(C++) - 백준(BOJ) 1595번 : 북쪽나라의 도로

https://www.acmicpc.net/problem/1595

1595번: 북쪽나라의 도로

dfs로 푼 문제였습니다.

 

📕 풀이방법

📔 입력 및 초기화

인접 도시로 가는 경로가 1개인 연결그래프는 트리입니다. 이 트리구조를 저장하기 위해 struct Edge를 만들어 양방향그래프를 저장합니다.

 

📔 풀이과정

예제 : 도시를 동그라미, 거리를 간선으로 표현한 그림

단순히 건너간 간선이 최대라고 거리까지 최대가 되지는 않습니다. 또한 어떤 도시에서 다른 도시로 갈때는 말단 노드(도시)를 경유지로 가면 안됩니다. 출발도시에서 말단 노드(도시)로 가는 거리들 중 최댓값을 구하기 위해서는 dfs방식이 구현이 쉽습니다.

 

 1. 트리의 정점 개수는 간선개수 + 1입니다. 따라서 간선과 거리정보를 입력할 때 마다 edgeCnt++해줌으로써 간선개수를 구할 수 있고 여기에서 + 1을 하므로써 정점 개수를 구할 수 있습니다.

 

 2. 1번 정점에서 ~ (간선개수 + 1)한 정점까지  각각 출발도시로 지정해 for문을 돌면서 dfs를 시행합니다. dfs는 말단노드로 갈 때까지 방문하지 않은 도시에 대해 cost에서 인접 정점으로 가는 거리를 더하면서 dfs함수를 재귀적으로 호출해줍니다. 이런식으로 호출하면서 출발도시에서 다른 말단 도시까지 가는 거리의 최댓값을 구할 수 있습니다. 이를 curCost에 저장합니다. 

 

 3. dfs함수가 끝나면 i도시 ~ 어떤 도시까지의 최댓값이 curCost에 저장되어 있으므로 정답을 출력할 maxAns에 max(기존값, curCost)를 저장합니다.

📔 정답출력

maxAns를 출력합니다.

---

📕 Code

#include <bits/stdc++.h>
using namespace std;
struct Edge{int v, w;};
vector <Edge> graph[10001];
int u, v, w, ck[10001], maxAns, edgeCnt, curCost;

void dfs(int cur, int cost){
    curCost = max(curCost, cost);
    ck[cur] = 1;
    int ret = 0;
    for(auto n : graph[cur]){
        if(ck[n.v]) continue;
        dfs(n.v, cost + n.w);
    }
}

int main(){
    while(cin >> u >> v >> w) {
        graph[u].push_back({v, w});
        graph[v].push_back({u, w});
        edgeCnt++;
    }

    for(int i = 1; i <= edgeCnt + 1; i++){
        memset(ck, 0, sizeof(ck));
        curCost = 0;
        dfs(i, 0);
        maxAns = max(maxAns, curCost);
    }

    cout << maxAns;
}