[ boj : 1595 ] 북쪽나라의 도로

[ boj : 1595 ] 북쪽나라의 도로

728x90

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

해설 : 이 문제는 엄청나게 유명한 웰논문제입니다. 그냥 트리의 지름을 찾는 문제이죠.

dfs 2번을 돌리면 답을 찾을 수 있다는 것이 증명이 되어있지만, 이번에는 tree dp 로 풀어보았습니다.

과정은 이렇습니다.

dfs를 돌리면서 부모-자식 간의 가중치를 return 시켜줍니다. 이때 루트노드까지 도달했을때는 넘겨받은 값들을 vector에 담아줍니다. 그러면 루트로부터 각 리프노드까지 거리가 얼마나 되는지 알 수 있겠죠?

그 vector를 sort 하여 2개를 뽑아줍니다. 이때 주의할 점은 정점이 단 2개만 존재할때는 0번 index만 뽑아오면 되고, 입력자체가 주어지지 않는 경우도 있더라구요. 이럴때 0을 출력해 주면 됩니다.

#include using namespace std; int visit[10010],child[10010]; vector> v[10010]; vector li; int dfs(int x); int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int x, y, w; while (true) { cin >> x; if (cin.eof())break; cin >> y >> w; v[x].push_back({ y,w }); v[y].push_back({ x,w }); } dfs(1); sort(li.begin(), li.end(), [](const int& a, const int& b) { return a > b; }); if (li.size() >= 2) cout << li[0] + li[1]; else if (li.size() == 1) cout << li[0]; else cout << 0; return 0; } int dfs(int x) { visit[x] = 1; for (int i = 0; i < v[x].size(); i++) { if (!visit[v[x][i].first]) { int ret = dfs(v[x][i].first) + v[x][i].second; if (x == 1) li.push_back(ret); child[x] = max(child[x], ret); } } return child[x]; }

728x90

from http://boomrabbit.tistory.com/176 by ccl(A) rewrite - 2021-09-17 22:01:09