BOJ 3176 도로 네트워크

코드 몬스터 2번이랑 유사한 문제라고 한다.

문제 분류는 LCA로 되어 있는데 LCA를 이용해서 어떻게 풀어야할지 감이 오지 않는다.

문제 설명
N개의 도시와 그 도시를 연결하는 N-1개의 도로로 이루어진 도로 네트워크가 있다.
모든 도시의 쌍에는 그 도시를 연결하는 유일한 경로가 있고, 각 도로의 길이는 입력으로 주어진다. -> 트리를 의미한다.

그리고 이제 k개의 도시 쌍이 주어지면, 두 도시를 연결하는 경로 상에서 가장 짧은 도로 길이와 가장 긴 도로의 길이를 구해야 한다.

일단 트리이기 때문에, 두 도시를 연결하는 경로는 유일하게 결정되고 그 경로는 반드시 두 도시의 LCA(최소 공통 조상)을 지날 것이다. 음... 저번에 슬랙에서 고수님들이 말씀하셨던 것을 다시 생각해 봤다.

 LCA에서 dp를 이용하는 O(logn)짜리 방식이 있는데,
그 방식의 경우 d[node][k] = node의 2의 k제곱번째 부모
였는데, 여기에 부모만 저장하는 게 아니라, 최소값(구하고자 하는게 최대값이면 최대값) 도 같이 저장하라고 하셨던 것 같다.

생각해보니 d[node][k]에 그 node부터 2의 k제곱번째 부모까지의 최소값을 저장한다면, 이 dp배열의 식을 조금만 수정하면 된다.
원래 식은 d[node][k] = d[d[node][k-1]][k-1] 이었는데,
node에서 2의 k제곱 번째 부모까지의 최소값
= MIN (node에서 2의 k-1제곱번째 부모 노드P 까지의 최소값, 노드P에서 2의 k-1제곱번째 부모까지의 최소값) 으로 하면 될 것 같다.

2의 k제곱 번째 부모를 구하는 것과 2의 k제곱 번째 부모까지의 최소값을 구하는 것은 따로 처리를 해줘야 한다.

두 정점사이의 경로는 결국 LCA를 기준으로 나뉘기 때문에, 즉, 각 정점의 부모를 거쳐 LCA를 찾는 과정이 곧 그 경로위에서 이루어지기 때문에 이렇게 LCA를 이용하면 (O(nlogn)의 dp배열 전처리만 해두면) O(logn)만에 두 정점 사이의 최소값을 구할 수 있을 것 같다.
 직접 구현해 봐야겠다.

겨우 AC를 받았다. 코드가 매우 복잡하다... parent[node][k]배열을
pair<int, pari<int, int> >로 해서 부모와, 최소값, 최대값을 다 저장하다보니...
그리고 계속 제대로 답이 안 나왔던 원인은... 바로 u, v의 최소 공통 조상을 찾으러 올라가면서 u와 v를 갱신해주는데, 일단 갱신전에 최소값, 최대값을 갱신해야 한다!! 최소, 최대를 갱신하기 전에 u, v를 갱신해버리니, 최소, 최대가 엉뚱한 값이 들어가게 되는 것이다.

다른 분들 코드도 좀 보고 공부해야겠다. 대충 봤는데, 나처럼 pair<int, pair<int, int> > 를 쓰지않고, struct를 쓰거나 배열을써서 0, 1, 2로 구분하거나 혹은 부모, 최소값, 최댁값을 각각 다른 3개의 배열로 하거나 하는게 더 가독성이 좋은 것 같다. 그리고 어떤 분은 parent[i][j-1]을 따로 변수로 받아서 쓰시는데 이것도 정말 좋은 것 같다.
나는 여태 이 생각도 못하고 parent[parent[i][j-1]][j-1]이러고 있었는데, 한 번만 쓰이면 상관없지만 이 문제에서는 최소값, 최대값까지 무려 3번이 쓰이므로 따로 변수로 받아쓰는 것이 깔끔하고 알아보기도 좋을 것 같다.
  그리고 주의해야할 점이 parent[i][j-1]값이 -1일 수도 있으니 -1이 아닌 경우만 보게 해야한다.
 좀 더 보기 좋게 고쳐서 다시 짜봐야겠다. 하면서 알게된 것인데, struct의 constructor를 이용하면 struct member를 처음부터 초기화 할 수 있다. (방법이나 종류가 여러가지가 있다.)
  난 이렇게 했다.

시간은 좀 느려졌지만 코드도 짧아지고, 실수도 많이 줄었다.