[BOJ][🟡3][백준#01888] 곰팡이

문제 출처

BAEKJOON Online Judge #1888

문제

벽에 곰팡이가 자라고 있다. 곰팡이들은 현재 여러 개의 덩어리를 이루고 있는 상태인데, 이들이 점점 자라나서 한 덩어리로 될 때까지 얼마의 시간이 걸릴지 알고 싶다. 이를 계산하는 프로그램을 작성해 보자. 곰팡이가 피어 있는 벽은 m행 n열의 격자로 나뉘어 있고, 한 칸 당 한 개의 곰팡이가 있다. 곰팡이의 덩어리라는 것은, 격자 상에 가로세로로 인접한 곰팡이들의 집합을 말한다. 맨 처음 상태에서는 한 덩어리 안의 곰팡이들이 모두 같은 종으로, 자라는 속도도 같다. 그러나 서로 다른 덩어리에 속한 곰팡이는 종이 달라 자라는 속도도 다를 수 있다. 또, 시간이 지남에 따라 서로 다른 종의 곰팡이 덩어리가 한 덩어리로 합쳐지는 경우도 있을 수 있다. 만약 어느 곰팡이의 자라는 속도가 k라면, 하루가 지났을 때 그 곰팡이가 피어있던 자리를 중심으로 2k+1행 2k+1열의 격자에 같은 종의 곰팡이가 번진다는 의미이다. 만약 서로 다른 종의 곰팡이가 같은 칸에 번져 오면, 자라는 속도가 빠른 곰팡이가 그 칸을 차지한다.

입력

첫 줄에 곰팡이가 피어 있는 벽의 크기를 나타내는 두 정수 m과 n이 주어진다. (1 ≤ m, n ≤100) 둘째 줄부터는 벽의 상황이 한 줄에 한 행씩 주어진다. 곰팡이가 피어있는 곳은 그 곰팡이의 자라는 속도로, 그렇지 않은 곳은 0으로 표시되어 있다. 자라는 속도는 1이상 5이하의 정수이다. 각 숫자 사이에는 빈 칸이 없다.

출력

첫 줄에 곰팡이가 한 덩어리가 되기까지 걸리는 시간을 하루 단위로 출력한다.

예제

입력

5 15
002000000000011
022000000011111
020000000010000
000000011110111
000000011110111

출력

2

My Sol

def main():
    def find_positions():
        positions = dict()
        for n in range(6):
            positions[n] = set()

        for i in range(I):
            for j in range(J):
                positions[mat[i][j]].add((i, j))

        positions.pop(0)
        nums = []
        for n in range(5, 0, -1):
            if positions[n]:
                nums.append(n)
            else:
                positions.pop(n)
        return nums, positions

    def get_all_values_set():
        all_values_set = set()
        for s in positions.values():
            all_values_set |= s
        return all_values_set

    def check_is_one():
        # 값이 있는 한 점 찾기
        all_values_set = get_all_values_set()
        fi, fj = all_values_set.pop()
        all_values_set.add((fi, fj))

        # 해당 좌표로부터 BFS
        visit = set()
        Q = {(fi, fj)}
        while Q:
            ni, nj = Q.pop()
            if (ni, nj) in visit: continue
            visit.add((ni, nj))
            for di, dj in ((-1,0),(1,0),(0,-1),(0,1)):
                si, sj = ni+di, nj+dj
                if not (0<=si<I and 0<=sj<J): continue
                if not mat[si][sj]: continue
                if (si, sj) in visit: continue
                Q.add((si, sj))

        # visit과 all_values_set이 같으면 one group
        other_group = all_values_set-visit
        return False if other_group else True

    def expand():
        for n in nums:
            expand_set = set()
            for ni, nj in positions[n]:
                for di in range(-n, n+1):
                    si = ni+di
                    for dj in range(-n, n+1):
                        sj = nj+dj
                        if not (0<=si<I and 0<=sj<J): continue
                        if mat[si][sj] >= n: continue
                        expand_set.add((si, sj))
            for ei, ej in expand_set:
                mat[ei][ej] = n

            for m in nums:
                if m==n:
                    positions[m] |= expand_set
                else:
                    positions[m] -= expand_set

    I, J = map(int, input().split())
    mat = [list(map(int, input())) for _ in range(I)]
    nums, positions = find_positions()
    day = 0
    while True:
        if check_is_one(): return day
        expand()
        day += 1

print(main())

여러모로 최적화를 위해 고민을 많이 했던 문제였다. BFS를 활용하는 문제였다. 모든 코드는 main 함수 내부에서 처리된다.

1. 가로 세로 곰팡이 2차원을 입력으로 받아준다.
2. 곰팡이 2차원 배열 mat의 각 좌표들을 모두 순회하며 곰팡이 종류와 좌표를 확인한다. 곰팡이 좌표를 모두 저장한 뒤, 값이 0이거나 좌표가 없는 값들은 dictionary에서 제거해준다. 이 곰팡이 종류(확장속도)를 모아둔 리스트는 nums, 각 종류를 key로 하고 좌표들을 set으로 저장하는 positions로 두었다. 이를 처리하는 함수는 find__positions 함수이다.
3. 확장이 없이도 하나의 그룹일 수 있기 때문에 0일부터 시작하여 한 덩어리인지 체크한다. 이를 check_is_one 함수라는 이름으로 확인했다.
4. mat을 모두 순회하지 않고, 보다 똑똑한 방법을 쓰기로 했다. 우선 positions의 모든 좌표들을 모아둔 set을 all_values_set으로 두었다. 이는 set의 합집합 연산으로 쉽고 빠르게 할 수 있다. 이후 이 set에서 한 좌표를 꺼내 상하좌우로 연결된 모든 값이 있는 좌표들에 대해 visit을 체크한다.
5. 이렇게 한 덩어리에 대해 체크하면 visit set에는 한 좌표에서 시작한 한 덩어리의 모든 좌표들이 저장될 것이다. 이를 전체 mat의 모든 값들을 모은 all_values_set과의 차집합을 구한다. 만약 mat 내의 곰팡이가 한 덩어리라면 visit set에는 모든 곰팡이의 좌표가 있을 것이고, 이미 모든 곰팡이의 좌표 set인 all_values_set와의 차집합은 빈 set이 될 것이다. 이를 통해 한 덩어리임을 확인했다.
6. 만약 check_is_one 이 True라면 day를 바로 반환하여 출력하면 되고, 아니라면 곰팡이의 확장이 시작된다. 이를 expand 함수로 구현했다.
7. 값이 큰 곰팡이 종류부터 확장을 시작하는데, nums에 곰팡이 종류를 지정할 때 내림차순으로 확인하며 값을 추가했으므로 해당하는 값부터 시작한다.
8. 해당 곰팡이 종류의 모든 좌표들의 확장 범위를 di, dj를 구해서 확장하려는 expand_set에 추가한다. 이는 한 곰팡이 종류를 시작할 때 초기화하여 범위를 벗어나지 않고, 값이 없거나 자기 종류보다 작은 값이 있는 좌표를 expand_set에 추가한다.
9. 이후 expand_set의 각 좌표를 모두 mat에 표시한다. 결국 해당하는 좌표로 해당 종류의 곰팡이가 확장할 것이기 때문이다.
10. positions에서 현재 확장하려는 곰팡이 종류의 set에는 expand_set의 합집합으로 만들어주고, 그 외의 곰팡이에 대해서는 expand_set를 빼서 차집합으로 만들어준다.
11. 이를 모든 곰팡이 종류에 대해 반복한다.
12. 확장을 마쳤다면 다시 위의 과정을 반복하며 한 그룹임을 확인하면 반복을 마치고 day를 출력한다.

결과

맞았습니다!!