[bj14868] 문명

문제

• 백준 URL: 문명
• 난이도 플래티넘 4

풀이

bfs를 진행하면서 각 문명에 대해 빈 공간일 경우 문명을 전파하고, 다른 문명일 경우 문명이 합쳐져있는 상태인지 확인하고, 서로 다른 문명일 경우 하나로 묶으면 될 것이라고 생각했다.
서로 다른 문명인지를 구별하고 문명을 묶는 방법은 유니온-파인드를 사용하면 될 것이라는 생각이 들었다.
따라서, 다음과 같이 기능을 구현하려고 했다.
1. 빈 공간일 경우 문명을 전파하고, 서로 다른 문명인 경우 문명을 결합하는 함수
2. 유니온-파인드 함수

문제는 1번인데, 문명을 전파하는 것과 문명을 결합하는 것을 한 함수로 구현하려고 했으나 선후관계 처리에 의해 함수를 둘로 나누는 것이 낫겠다는 생각이 들었다.
따라서 다음과 같이 함수를 구현했다.

def bfs(q):
    q_next = deque([])
    while q:
        x,y = q.popleft()
        civ = l[x][y]
        for dx,dy in di:
            nx,ny = x+dx,y+dy
            if 0 <= nx < n and 0 <= ny < n:
                if not l[nx][ny]:
                    l[nx][ny] = civ
                    q_next.append((nx,ny))
    return q_next

def civ_combine(q):
    for node in q:
        x,y = node
        civ = l[x][y]
        for dx,dy in di:
            nx,ny = x+dx,y+dy
            if 0 <= nx < n and 0 <= ny < n:
                if l[nx][ny] and l[nx][ny] != civ:
                    u(civ, l[nx][ny])

def f(a):
    if a!=parent[a]:
        parent[a] = f(parent[a])
    return parent[a]

def u(a,b):
    global civ_cnt
    rootA = f(a)
    rootB = f(b)
    if rootA != rootB:
        if rootB > rootA:
            parent[rootB] = rootA
        else:
            parent[rootA] = rootB
        civ_cnt -= 1

bfs() 함수는 문명을 전파하기 위한 함수이며, civ_combine() 함수는 문명을 결합하기 위한 함수이다. 그리고 u()와 f()는 전형적인 유니온-파인드 함수이다. 서로 다른 문명을 만났을 때 parent가 다른 경우 결합되지 않은 것으로 확인하고, 서로의 parent를 통합하며 civ_cnt를 1씩 줄인다. 이러한 결합 과정을 반복하다가 civ_cnt가 1이 되면 문명이 모두 결합되어 하나만 남았다는 것을 알 수 있다.

from collections import deque

n,k = map(int, input().split())
l = [[0]*n for _ in range(n)]
civ_node = deque([])
civ_cnt = k
times = 0
parent = [i for i in range(k+1)]
di = [(1,0),(-1,0),(0,1),(0,-1)]
for i in range(k):
    x, y = map(int, input().split())
    l[x-1][y-1] = i+1
    civ_node.append((x-1,y-1))
    
def bfs(q):
    q_next = deque([])
    while q:
        x,y = q.popleft()
        civ = l[x][y]
        for dx,dy in di:
            nx,ny = x+dx,y+dy
            if 0 <= nx < n and 0 <= ny < n:
                if not l[nx][ny]:
                    l[nx][ny] = civ
                    q_next.append((nx,ny))
    return q_next

def civ_combine(q):
    for node in q:
        x,y = node
        civ = l[x][y]
        for dx,dy in di:
            nx,ny = x+dx,y+dy
            if 0 <= nx < n and 0 <= ny < n:
                if l[nx][ny] and l[nx][ny] != civ:
                    u(civ, l[nx][ny])

def f(a):
    if a!=parent[a]:
        parent[a] = f(parent[a])
    return parent[a]

def u(a,b):
    global civ_cnt
    rootA = f(a)
    rootB = f(b)
    if rootA != rootB:
        if rootB > rootA:
            parent[rootB] = rootA
        else:
            parent[rootA] = rootB
        civ_cnt -= 1

while 1:
    civ_combine(civ_node)
    if civ_cnt == 1: break
    civ_node = bfs(civ_node)
    times += 1

print(times)