[백준 14868번] 문명 (Python3)

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위가 되었다.