Baekjoon 7644

문제(Baekjoon)

내 코드(Github)

상부에 조르고 졸라 드디어 내 도시에도 고속도로가 들어서게 되었다. 만세!

문제는, 그냥 다들 한곳에 모여살면 좋을것을 서로 원수라도 졌는지 공동체들이 여기저기 흩어져 있다는 것.

공동체들은 각각 유일한 번호로 이름지어져 있고, 각 공동체들을 잇는 도로가 존재한다.

한 공동체에서 다른 공동체로 갈 수 있는 경로는 꼭 하나만(가) 존재한다.

우리는 이 도로중 일부를 대체할 하나의 선으로 이루어진 고속도로를 짓는다. 고속도로에서 떨어져있는 공동체는 어쩔 수 없이 기존에 존재하던 도로를 이용해 고속도로에 접근해야한다.

고속도로에서 가장 멀리 떨어진 공동체에서 고속도로까지의 거리를 최소화하는 방향으로 고속도로를 건설하였을 때, 그 거리는 얼마인가?

내 가정:

각 노드에서 다른 노드까지의 경로가 단 하나만(가) 존재한다는 것으로 보아 이 그래프는 트리이다.

고속도로는 그래프의 한 종단노드에서 다른 종단노드까지의 경로를 잇는 선이다.

각 종단노드들을 루프토드로 잡고 아래로 탈탈 털어 트리모양으로 만든 후, 각 루프노드에서 각 리프노드까지 경로의 코스트를 구한 경우의 수들 중, 코스트가 가장 큰 경로^[각주:1]를 우리가 지을 고속도로로 한다.

이제 고속도로가 지나는 노드 중, 고속도로에 접하지 않은 노드를 갖는 노드들을 루프노드들로 하고, 고속도로가 이어지지 않은 리프노드들까지의 코스트들을 구해 가장 큰 값을 취한다.

09/24/2018

풀이:

트리의 지름을 구하는 문제이다.

트리의 지름의 각 끝점이 되는 두 종단노드를 구한 후, 해당 두 종단노드를 잇는 경로에서 두 종단노드를 제외한 다른 종단노드까지의 거리중 가장 큰 값을 구하면 된다.

트리의 지름의 각 끝점이 되는 두 종단노드 x, y를 구한 후, x, y를 잇는 경로의 cost를 0으로 설정, x부터 시작해 트리를 DFS하여 가장 큰 코스트를 출력하였다.

1. 틀렸나? [본문으로]