IOI 2012 Day 2 Task 1 : City (이상적인 도시)

Baekjoon Online Judge 링크(5813)

어떤 이상적인 도시가 있다. 이 곳은 구획들이 블럭으로 이루어지는데, 이 도시에는 구멍이 없다.
즉 블럭이 없는 곳 사이에는 항상 경로가 있고, 블럭끼리도 항상 경로가 있다.
블럭들간의 최단 경로의 합을 구하는 문제이다.

처음에 생각하기로는 도시에서 튀어나온 부분을 고려하면서 조금씩 제거한다든가 하는 걸 생각해봤는데, 너무 복잡하더라.

정해에 가까운 해답을 생각했으나 코딩력이 딸려서(...) 그걸 실제로 구현하려는 생각은 못했었다.

예제이다.

먼저, 두 점 사이에 x축 상으로 움직이는 거리를 살펴보자.

이렇게 보면 두 점 사이에 x축에 평행하게 움직이는 거리는 두 노드 사이의 거리와 정확히 같다.

그런데 전체에 구멍이 없고, 전체가 연결되어 있기 때문에,

잘 생각해보면 이는 항상 트리가 된다.

그러면, 모든 점간의 이동거리 중 x축상의 이동거리는 이 트리에서 각 노드간 거리의 합이 된다.

트리에서 각 노드간 거리의 합은 쉽게 구할 수 있다!

따라서, 이렇게 각 축에 대해,

그 축에 수직한 방향으로 연속한 점들을 한 노드로 묶은 뒤,

각 노드간에 움직이는 거리의 합을 다 더하면 답이 된다.