이 문제는 어렵다. 완벽히 이해한 것도 아니다.
일단 나중에 다시 볼 때를 위해서 지금까지 이해한 것을 적어보려 한다.
이 문제는 IOI 2013 Day1문제인데, 어렵고 쉽고를 떠나서 (나에게는 매우 어렵지만) 배울게 많은 문제였다. 바로 트리에 관한 여러 용어와 개념들, 특성 그리고 증명(그렇게 되는 이유) 등을 알고 이해해야 풀 수 있는 문제같다.
문제를 푸는데 필요한 개념의 용어 정리 부터 하자면,
트리의 지름 - 트리에서 가장 긴 경로
트리의 중심 - 트리의 각 노드로 부터의(에서 시작하는) 가장 긴 경로들 중 최소인 경로가 있는데, 그 경로의 시작점 노드를 트리의 중심이라고 한다. 원래 있는 용어인지는 확실치 않지만, 이 경로를 트리의 반지름이라고 하는 것 같다.
중요한 성질 중 하나가 트리의 반지름과 트리의 중심은 트리의 지름 위에 있다는 것(겹친다는 것)인데, 트리의 중심은 트리의 지름에서 거리상으로(정점의 개수로 판단하는 것이 아님) 가운데에 있는 노드이다.
트리의 지름을 구하는 법은 널리 알려져있고, 간편하고 쉬운 방법이 있는데, 이 문제에서 큰 난관은(물론 가장 큰 문제는 답을 어떻게 구할지이겠지만, 난 myungwoo님 블로그를 통해서 그냥 풀이를 봤다.) 반지름을 어떻게 구하냐였다. 나는 일단 지름을 dfs를 2번 돌려서 구하고(dfs 한 번에 구하는 방법도 있어서 뒤에 적어보겠다.) 지름을 구하면서 지름을 구성하는 노드들을 순서대로 저장하고, 한쪽 끝 노드에서 출발해서 거리(가중치)를 더해가면서 거리상으로 중심이 되는 노드를 찾았다. 근데 한쪽 에서만 하면 안되고 양쪽에서 각각 중심까지의 거리(반지름)을 구해서 더 작은 것을 택해야 한다. - 이렇게 푸니... 코드가 지저분해지고 신경써야할 것들도 많아지고 실수도 좀 하게 되었다.
그러던 중 이에 대해 설명과 증명이 잘 나와있는 블로그(codingishard님의 블로그)를 통해 어느정도 깨달음을 얻었고, 여태 내가 지름을 구했던 방법이나, 지름을 구하기 위해 dfs를 하는 방법보다 더 좋아보이는 방법을 이해하고 배우게 되었다.
1.dfs
나는 트리를 dfs로 순회할 때, visited배열을 이용해서 방문하면 true로 만들고, 한 번 방문한 node는 다시 방문하지 않게 해서 child에서 parent로 올라가지 않도록 했는데, 이렇게 하면 다시 root부터 탐색을 할 때 visited배열을 다시 초기화 해줘야 한다. 하지만 parent배열을 이용하면 처음에는 parent배열에 자기자신으로 초기화 해두고, dfs를 하면서 방문하는 node는 자신의 parent로 배열을 초기화 해준다. 그러면 자신과 연결된 노드들을 방문하려고 할 때, 자신의 parent배열을 보고 자기자신의 parent가 아니면 방문하는 식인데, 이렇게 하면 다음에 다시 root에서 시작할 때 parent배열을 초기화 할 필요가 없다.
하지만 root가 아닌 다른 점을 root로 해서 시작하고 싶을 때는 parent배열을 초기화 해줘야 한다. 어떻게 보면 이렇게 parent배열을 이용하는 것은 한 root를 기준으로 트리를 구성하는 것으로도 볼 수 있겠다.
그런데 이 parent배열조차 이용하지 않고 할 수 있는 방법이 있다. 바로 dfs함수를 호출할 때, parameter로 그 node의 parent인 node의 번호를 보내는 것이다. dfs(node, parent)이렇게 말이다. 그러면 child를 탐색하려고 할 때 자신의 parent가 아닌 node만 탐색하면 된다. 이 경우 따로 check하는 배열을 둘 필요도, 다시 탐색할 때 무언가를 초기화할 필요도 없다.
- 코드를 짜보면서 이렇게 해보려고 했는데, 이 빌라봉 문제처럼 트리가 여러개 존재하는 경우, 불필요한 dfs탐색을 할 수 있어서 경우에 따라 배열을 이용하는 것이 나아보인다.
- 하지만 이 빌라봉 문제의 경우 codingishard님의 코드를 보면 지름을 구하는 함수를 콜한 후 바로 반지름을 구하는 함수를 콜한다. 그렇기 때문에 지름을 구하는 함수는 위의 방식으로 하고, 반지름을 구하는 함수에서만 check배열을 써서, 지름을 구하는 함수도 check배열의 혜택(?)을 받아 불필요한 dfs탐색이 없다...!
2. 트리의 지름 구하기
트리의 지름을 구하는 것을 dfs 한 번만에 하려면 일단, 트리의 지름의 특성을 잘 생각해봐야 한다. 트리의 지름은 트리 내에서 노드와 노드 사이의 가장 긴 경로인데, 가장 긴 경로가 되려면 leaf node - leaf node이거나 root node - leaf node 이여야 한다. 보통 leaf node - leaf node로 보면 된다.
방법을 설명하면, dfs로 트리를 root부터 순회하면서 각node를 포함하는 가장 긴 경로를 구해서 그 중 최대 경로를 찾으면 되는 것인데, 각 node를 포함하는 가장 긴 경로는 각 child를 root로 하는 subtree의 높이들(가장 긴 경로들)중에서 가장 큰 2개의 높이와 node로 부터 그에 해당하는 child까지의 거리의 합으로 구할 수 있다.
각 subtree의 높이(child root에서 시작하는 가장 긴 경로)의 값과 그 subtree에서의 지름을 구해 현재 tree의 가장 긴 경로를 구하고 subtree의 지름과 비교해서 현재 트리의 지름을 구하는 식으로...재귀적으로 풀 수 있다.
3. 트리의 반지름 구하기
이 부분은 따로 설명이 없어서 이해하기 좀 어려웠는데, 계속 보고 따라쳐보고 생각해보니 좀 이해가 됐다. 반지름은 node가 3개 이상일 때는 항상 internal node-leaf node로 볼 수 있다. (root node는 internl node나 leaf node 둘 중 하나로 볼 수 있겠다.) 그래서 root node부터 시작해서 그 node에서 시작하는 가장 긴 경로들을 구하고 그 중에 최소값을 찾으면 그것이 반지름의 길이가 된다. 그럼 어떻게 한 node에서 시작하는 가장 긴 경로들을 구할 것인가? 위에서 트리의 지름을 구할 때 subtree의 높이들(subtree의 root node에서 시작하는 가장 긴 경로들)을 구했는데, 그것을 저장해놨다가 반지름을 구할 때 이용하면 된다.
여기서 좀 까다로운 것이, (node의 각 child를 root로 하는 subtree의 높이)+ (node부터 그 child까지의 cost) 값들을 즉, node부터 시작하는 가장 큰 경로들을 집합A라고 하면, 그 중에서 가장 큰 경로가 node에서 시작하는 가장 큰 경로의 길이인데, child에서 시작하는 가장 큰 경로의 길이를 구하려면 집합A에서 가장 큰 경로가 필요하다.
child에서 시작하는 가장 큰 경로는 max( (node에서 시작하는 가장 큰 경로)+(node에서 child까지의 cost) , (child를 root로 하는 subtree에서 child부터 시작하는 가장 큰 경로) ) 이다. ->자신의 parent쪽으로 가장 큰 경로와, 자신의 child쪽으로 가장 큰 경로 중 최대값을 뜻한다. 이렇게 각 node에서 시작하는 가장 큰 경로를 구하고, 그 중 최소값을 구해야 하는 것이다.
다시 정리하면, 이 함수는 각 root부터 시작해서 root부터 시작하는 가장 큰 경로를 구하고, 재귀적으로 root의 child들의 subtree에서의 가장 큰 경로들과 비교해서 최소인 값 즉 반지름 값을 return하는 함수이다.
반지름 구하는 과정은 많이 헷갈린다... 일단 무조건 한 node에서 시작하는 가장 큰 경로를 구해야하고 , 그것들을 비교해서 그 중 가장 작은 것을 고르는 과정이라고 보면 된다.
4. 여러 개의 값들 중 가장 큰 값 2개를 구하는 방법
난 무조건 sorting을 했는데, 그럴 필요없이 for문을 돌리면서 가장 큰 값을 a에 넣고, 더 큰 값이 나오면 a의 값을 b에 넣고 a는 다시 가장 큰 값을 취하는 식으로 하면 큰 순서대로 2개의 값 a, b를 구할 수 있다. 물론 값 3개도 이런 방식으로 구할 수 있다!
5. 증명은 대부분 귀류법으로 하는 것 같다. 그리고 내가 고민했던 것 중 하나가 트리의 지름이 여러개일 경우 트리의 반지름이나 중심을 구하려면 여러개의 트리의 지름에서 찾은 후 비교해서 가장 작은 값이 되는 쪽을 선택해야 하는 것 아닌가에 대한 것인데, codingishard님의 블로그에서 "트리의 지름을 결정하는 여러 경로들은 반드시 반지름을 결정하는 정점을 교점으로 지나간다는 특성" 때문에 괜찮다고 나와있고, 또한 귀류법으로 증명할 수 있다고 나와있다.
참조
http://blog.myungwoo.kr/8
https://www.quora.com/What-is-the-solution-for-Dreaming-on-IOI-2013
http://blog.sisobus.com/2013/10/backjoon-online-judge-no1967.html#.V9DM_a2vYqO
http://codingishard.tistory.com/m/1
댓글 없음:
댓글 쓰기