인류의 역사를 돌이켜보면, 문명의 발전은 독자적으로 진행되기도 하지만 서로 다른 문명이 만나 결합되기도 한다. 여러분은 이 가설을 바탕으로, 세계 문명의 발전 과정을 시뮬레이션 해보려고 한다.
세계를 N × N의 2차원 공간으로 생각할 수 있다. 즉, 1×1 크기의 정사각형이 가로, 세로로 각각 N개씩 쌓여있는 형태로 생각할 수 있다. 가장 왼쪽 아래 정사각형은 (1,1), 가장 오른쪽 위 정사각형은 (N,N) 위치에 있다. 두 정사각형 (a, b)와 (a′, b′)은 다음 두 조건 중 하나만 만족할 때 서로 인접해 있다고 하자.
|a - a′| = 1 이고 b = b′. |b - b′| = 1 이고 a = a′. 문명의 최초 발상지는 모두 서로 다른 K곳에 있다. 각 정사각형에 해당하는 공간은 문명 지역이거나, 미개 지역이다. 문명의 최초 발상지는 문명 지역이며, 만약 문명 최초 발상지끼리 인접해 있다면, 이들은 처음부터 하나로 결합된다. 한 해가 지날 때마다, 문명 지역은 자신과 인접한 지역에 문명을 전파한다. 정사각형 (a, b)가 문명 지역이면, 다음 해에는 세계의 경계를 넘지 않는 한 이 정사각형과 인접한 네 정사각형 (a+1, b), (a-1, b), (a, b+1), (a, b-1)에 문명이 전파된다. 만약 두 인접하는 지역에 다른 문명이 전파되었거나, 한 지역에 둘 이상의 다른 문명이 전파된다면 이 문명들은 결합된다.
예를 들어, 다음과 같이 5 × 5 크기의 세계에 4곳의 정사각형 (1, 1), (2, 1), (2, 5), (5, 2)가 문명의 발상지라고 하자. 정사각형 (1, 1), (2, 1)의 문명은 인접해 있으므로 처음부터 결합되어 있다. 1년후 문명이 전파된 지역은 오른쪽 그림과 같고, 2년 후에 문명이 전파된 지역은 아래 그림과 같다. 이때 모든 문명은 서로 결합되어 하나의 문명이 된다. (2, 5)에서 발상한 문명과 (5, 2)에서 발상한 문명은 직접적으로 결합되지는 않았지만, (1, 1),(2, 1)에서 발상한 문명을 통하여 결합됨에 주의하라.
세계의 크기, 문명 발상지의 수 및 위치를 입력으로 받아 모든 문명이 하나로 결합될 때까지 걸리는 최소 햇수를 구하는 프로그램을 작성하시오.
표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 세계의 크기를 나타내는 정수 N(2 ≤ N ≤ 2,000)과 문명 발상지의 수 K(2 ≤ K ≤ 100,000)가 주어진다. 다음 K줄에는 한 줄에 하나씩 문명 발상지에 해당하는 정사각형의 위치 (x, y)를 나타내는 두 자연수 x와 y가 주어진다. (1 ≤ x, y ≤N)
출력
표준 출력으로 모든 문명이 하나로 결합되는데 걸리는 최소 햇수를 정수로 출력한다.
입력 예시
5 4
1 1
2 1
2 5
5 2
출력 예시
2
풀이
문명 탐색을 진행하되, 접촉한 문명이 같은 문명을 판단할 방법이 필요하다. 즉 유니온 파인드를 수행할 필요가 있다. 만약 두 문명이 인접 조건을 만족했고, 두 문명의 루트 문명(find)이 다르다면 두 문명을 합치고 총 문명 수를 1 줄여주여야 한다. 이를 너비 우선 탐색으로 진행하고, 문명 수가 1이 될 때까지 반복하면 된다.
풀이 코드
import sys
input = sys.stdin.readline
dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]
N, K = map(int, input().split())
civil_maps = [[0]*N for _ in range(N)]
civil = K
parents = list(range(K+1))
def find(a) :
if a == parents[a] :
return a
parents[a] = find(parents[a])
return parents[a]
def union(pa, pb) :
if pa > pb :
pa, pb = pb, pa
parents[pb] = pa
def merge_civils(a, b) :
global civil
pa, pb = find(a), find(b)
if pa != pb :
civil -= 1
union(pa, pb)
def bfs(q) :
global civil
next_q = []
while q :
x, y, c = q.pop()
for i in range(4) :
ax, ay = x + dx[i], y + dy[i]
if not (-1 < ax < N and -1 < ay < N) :
continue
if civil_maps[ay][ax] :
merge_civils(c, civil_maps[ay][ax])
continue
civil_maps[ay][ax] = c
next_q.append((ax, ay, c))
for j in range(4) :
bx, by = ax + dx[j], ay + dy[j]
if -1 < bx < N and -1 < by < N and civil_maps[by][bx] :
merge_civils(c, civil_maps[by][bx])
return next_q
q = []
cnt = 1
for _ in range(K) :
x, y = map(int, input().split())
x -= 1
y -= 1
civil_maps[y][x] = cnt
for i in range(4) :
ax, ay = x + dx[i], y + dy[i]
if -1 < ax < N and -1 < ay < N and civil_maps[ay][ax] :
merge_civils(cnt, civil_maps[ay][ax])
q.append((x, y, cnt))
cnt += 1
t = 0
while civil > 1 :
t += 1
q = bfs(q)
print(t)
