[백준 - Python] 2638 - 치즈

0.  문제 링크

 

 

 

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

2638번: 치즈

---

1.  풀이 방법

 

 

1. 문제에서는 맨 가장자리엔 치즈가 없다라고 되어있다. 따라서 BFS의 시작은 맨 가장자리인 [0][0]에서 시작한다.
2. 치즈와 인접한 공기를 체크하기 위해 adjCheck를 사용했다. 해당 리스트는 치즈와 인접한 공기의 개수를 체크한다.
3. 공기의 중복 방문 처리를 위하여 airCheck를 사용했다. 해당 리스트는 공기가 이미 방문한 곳을 처리한다.
4. 결론적으로 BFS를 공기 기준으로 돌면서 방문한 곳에 치즈가 있다면 adjCheck에 치즈의 위치에 + 1을 더한다.
5. 치즈에 인접한 공기가 2개 이상이 된다면 Set에 넣는다. 이렇게 함으로써 치즈가 중복적으로 입력되는 것을 막는다.
6. 아이디어의 핵심은 다음 라운드에 공기가 될 예정인 치즈만 다시 BFS로 확인해서 adjCheck를 업데이트하면 된다는 것이다.
7. 위 아이디어와 알고리즘을 반복적으로 한다면 정답이다.

---

2.  코드

 

 

import sys
from collections import deque
input = sys.stdin.readline


def adjAirCheck(dq):
    nextSet = set()
    while dq:
        y, x = dq.popleft()
        for dy, dx in dir:
            ny, nx = y + dy, x + dx
            if 0 <= ny < n and 0 <= nx < m:
                if maps[ny][nx] == '1':      # 치즈라면
                    adjCheck[ny][nx] += 1
                    if adjCheck[ny][nx] >= 2:       # 인접한 공기가 2개
                        nextSet.add((ny, nx))
                else:
                    if airCheck[ny][nx] == False:       # 공기가 방문하지 않았다면
                        airCheck[ny][nx] = True
                        dq.append((ny, nx))
    
    return nextSet


if __name__ == "__main__":
    n, m = map(int, input().split())
    maps = [input().strip().split() for _ in range(n)]
    airCheck = [[False] * m for _ in range(n)]      # 공기의 방문 체크
    adjCheck = [[0] * m for _ in range(n)]      # 치즈에 인접한 외부 공기의 개수

    cnt = sum([i.count('1') for i in maps])

    dir = [[0, 1], [0, -1], [1, 0], [-1, 0]]

    dq = set()
    dq.add((0, 0))
    airCheck[0][0] = True
    time = 0

    while cnt > 0:
        time += 1
        dq = deque(dq)
        dq = adjAirCheck(dq)
        cnt -= len(dq)
        
        for y, x in dq:
            maps[y][x] = '0'
            airCheck[y][x] = True

    print(time)

---

3.  마무리