BOJ 5813: 이상적인 도시

Link

• https://www.acmicpc.net/problem/5813

• IOI 2012 Day2 1번

Tag

• 트리

Time Complexity

• $O(NlgN)$ / $O(N)$

네모 셀들로 이루어진 무한한 이차원 격자에 N개의 블록들을 놓았다. 비어 있는 셀들과 비어있지 않은 셀들은 각각 오직 하나의 컴포넌트를 이룬다. 이때 모든 두 블록 쌍에 대한 최단거리의 합을 계산해야 한다.

 

비어있는 셀들과 비어있지 않은 셀들이 각각 하나의 컴포넌트를 이룬다는 말은, 구멍이 없다는 말이다.

X좌표가 같은 인접한 블럭들의 토막을 노드로 보고, 간선으로 이어 그래프를 만들면 문제 조건에 의해 트리가 된다. 이 트리 상에서 모든 두 정점 쌍의 거리의 합은, 모든 두 블록 쌍에 대한 최단거리의 Y좌표 합과 같다. 트리의 모든 두 정점 쌍의 거리의 합을 구하는건 Tree DP 느낌으로 dfs 한번에 구할 수 있다. X좌표의 합도 같은 방법으로 구할 수 있다.

 

트리를 만드는게 은근 귀찮은데, $O(N)$으로 만들 수도 있지만 난 그냥 뇌비우고 $O(NlgN)$에 했다.

Code