백준 14868 문명 파이썬

https://www.acmicpc.net/problem/14868

​

​

문명은 전파된다고 한다. 문명이 전파되었을 때, 문명끼리 다 만나는 시점을 구하는 문제다. 단순히 생각해봤을 때, 문명이 전파하고 문명이 만난 것을 표현해주려면 현재 그래프에서 문명의 값을 설정해주고, 만날 때 마다 문명의 값을 흡수되는 쪽으로 다 바꿔주면 된다.

​

쉽게 얘기하면 위의 그림처럼 되면 된다. 1,2가 만나면 모든 2가 1로 바뀌는 것이다. 아주 단순한 방법이다. 그런데 이렇게 할 경우 큰 문제점이 생긴다. 바로 너무 비효율적이라는 것이다.

​

현재 문명은 20만개가 주어질 수 있다고 한다. 그리고 전체 맵은 2000 * 2000으로 4,000,000 칸을 보여준다. 맵에 모두 업데이트 한다고 하면 최악의 경우 4,000,000 * 200,000의 경우의 수를 감당해야한다. 안된다.

​

그렇다면 어떻게 문명과 문명이 나누어졌는지를 구분할 수 있을까? 분리집합을 이용하면 된다. 분리집합은 Union Find라고도 하는데 구글링하면 잘 나온다.

​

분리집합을 하면서, 각 집단이 대표값을 가지게 한다. 그래서 문명과 문명이 만났을 때 대표값을 서로 꺼내보이고, 대표값이 같으면 우리는 같은 집단이고, 다르면 다른 집단이라고 서로 인식을 하는 것이다. 그리고 다른 집단인 경우 문명이 전파되기 때문에 같은 그룹으로 만들어주면 된다.

​

나 같은 경우에는 같은 그룹을 만들어 줄 때, 좀 더 효율적으로 하기 위해서... 유니온 파인드를 할 때 현재 같은 그룹에 속해있는 문명의 갯수를 세었고, 결국에는 0번 문명으로 모두 합쳐지는 방식으로 했다. 그래서 0번 문명이 가지고 있는 문명의 갯수가 K개가 되는 시점을 종료조건으로 설정했다.

 

import sys
from collections import deque

def find(x, x_num) :

    # 루트 넘버 도착 시, 현재 값을 더해준다.
    # 루트 넘버 반환
    if k_list[x] == x :
        n_list[x] += x_num
        return x

    else :
        next_x_num = n_list[x] + x_num

        # 합쳐 졌으니, Count는 넘겨준다.
        n_list[x] = 0

        # 루트값을 현재 노드에 저장해둔다.
        k_list[x] = find(k_list[x],next_x_num)

        return k_list[x]

def union(x,y) :
    xx = find(x, 0)
    yy = find(y, 0)

    # 0을 기준으로 루트 넘을 합쳐준다.
    # 0에서 종료조건임.
    if xx > yy :
        # root_num끼리 합쳐줘야함.
        k_list[xx] = yy
        find(xx,0)
    else :
        k_list[yy] = xx
        find(yy, 0)

    return

#문명 전파
def bfs(city):
    que = deque()
    while city :
        a,b,city_num = city.pop()
        que.append((a,b,city_num))

    while que :
        r,c,city_num = que.popleft()

        for rr,cc in tra_list:
            next_r, next_c = r + rr, c + cc

            if -1 < next_r < n and -1 < next_c < n:
                if my_list[next_r][next_c] == -1 :
                    my_list[next_r][next_c] = city_num
                    city.append((next_r, next_c, city_num))



#이웃한 문명끼리 유니온 파인드 대상인지 확인
def union_find(city):

    for r,c,city_num in city:
        for rr, cc in tra_list:
            next_r, next_c = r + rr, c + cc
            if -1 < next_r < n and -1 < next_c < n:

                next_city_num = my_list[next_r][next_c]


                #Union Find 대상
                if my_list[next_r][next_c] != -1 and city_num != next_city_num :
                    union(next_city_num, city_num)


tra_list = [[1,0],[-1,0],[0,1],[0,-1]]


n,k = map(int,sys.stdin.readline().split())
# 분리 집합 루트보관
k_list = [q for q in range(k)]
# 분리 집합 현재 가지고 있는 갯수 보관
n_list = [1 for _ in range(k)]
my_list = [[-1 for _ in range(n)] for _ in range(n)]
city = []
for cnt in range(k):
    a,b = map(lambda x:x-1, map(int,sys.stdin.readline().split()))
    my_list[a][b] = cnt
    city.append((a,b,cnt))


day = 0


# 초기 조건 경계 조건 클리어

union_find(city)

while n_list[0] != k :
    day += 1

    # 영토 확장
    bfs(city)

    # 분리집합 처리
    union_find(city)

print(day)