import sys,collections
input = sys.stdin.readline
dy = [1,-1,0,0]; dx = [0,0,1,-1]
def BFS():
connect = 0
while dq:
y,x,k,t = dq.popleft()
if visited[y][x]:
continue
visited[y][x] = k
for i in range(4):
y1,x1 = y+dy[i],x+dx[i]
if N>y1>=0 and N>x1>=0:
k1 = visited[y1][x1]
if k1:
if find(k)==find(k1):
continue
parent[parent[k1]] = parent[k]
connect += 1
if connect == K-1:
return t
else:
dq.append((y1,x1,k,t+1))
def find(x):
if parent[x]!=x:
parent[x] = find(parent[x])
return parent[x]
N,K = map(int,input().split())
visited = [[0]*N for i in range(N)]
dq = collections.deque()
for k in range(1,K+1):
dq.append((*map(lambda x:int(x)-1,input().split()),k,0))
parent = [i for i in range(K+1)]
print(BFS())
BFS + union-find로 해결하였다.
아이디어도 간단하고 구현도 어렵지 않은 문제
풀이를 설명하면,
1. deque에 각 문명의 시작지점의 좌표 + 문명의 번호 + 0을 튜플로 저장한다.
2. BFS를 한다. visited에는 각자 문명의 번호를 기록한다.
3. BFS 도중 현재 위치의 4방향에서 현재 문명과 union되지 않은 문명을 만날 경우 connect 변수에 +1을 하고 union한다.
4. connect 변수가 N-1이 되면 모든 문명이 연결된 것이므로 시간을 출력한다.
여담) 이 문제 숏코딩 순위 1위가 되었다.