[백준] 2638 치즈 (BFS) - Python

 

2638번: 치즈

 

- 문제 설명

• 2차원 배열 모눈종이 위에 치즈가 존재한다.
• 어떤 칸에 존재하는 치즈가 2칸이상 치즈가 아닌 칸 (외부 공기)로 접촉하여 있다면
  그 칸의 치즈는 1시간 후 녹아 사라진다.
• 치즈 속에 존재하는 빈칸(치즈 속 공기)는 외부공기에 접촉하지 않았다고 생각한다.

• 위 그림을 보면 외부 공기와 2칸 이상 접촉한 치즈는 사라졌고
  내부공기와 접촉한 치즈는 그대로 존재한다.

 

- 접근방법

• 또다시 BFS로 풀어야겠다는 생각이 들었다.
• 내부 공기와 외부공기는 똑같이 0으로 입력되지만 둘을 구분해야하므로
  항상 치즈가 없는 가장자리에서 BFS 탐색을 진행해 외부공기를 표시한 리스트를 만든다.
• 치즈가 있는 모든 칸에서 델타 탐색을 통해 외부공기가 2칸 이상 닿아있는지 체크한다.
• 2칸 이상 닿아있다면 치즈가 녹아 사라졌다고 갱신해준다.
• 모든 칸에 탐색을 진행했다면 시간이 한시간 지났다고 체크하고 다시 반복한다.
• 다시 반복시 치즈가 녹아 내부공기와 외부공기가 합쳐졌을 수 있으므로
  외부공기 리스트를 초기화하여 BFS를 다시 진행한다. 
• 종이 위에 치즈가 없다면 반복을 종료한다.

 

- 입출력 예시

 

- 코드

from collections import deque

dr = [-1, 1, 0, 0]
dc = [0, 0, -1, 1]
# 치즈 밖에있는 공기를 탐색하는 함수
def bfs(r, c):
    global air
    q = deque()         # 공기층 탐색을 위한 큐
    q.append((r, c))    # 현재위치 저장
    # 공기층 초기화
    air = [[0] * M for _ in range(N)]
    air[r][c] = 1

    while q:
        i, j = q.popleft()
        # 4방향 탐색
        for d in range(4):
            nr, nc = i + dr[d], j + dc[d]
            # 탐색한 위치가 유효범위이고, 치즈가 없고, 방문한적이 없다면
            if 0 <= nr < N and 0 <= nc < M and paper[nr][nc] != 1 and not air[nr][nc]:
                q.append((nr, nc))      # 큐에 추가
                air[nr][nc] = 1         # 방문처리

N, M = map(int, input().split())
paper = [list(map(int, input().split())) for _ in range(N)]
air = [[0]*M for _ in range(N)]     # 치즈 바깥의 공기표현할 리스트

time = 0        # 걸린시간
while True:
    # 가장자리에서 공기층 탐색
    bfs(0, 0)
    cheese = 0      # 치즈가 있는지
    for i in range(N):
        for j in range(M):
            cnt = 0     # 4방향안에 공기층 개수를 셈
            if paper[i][j] == 1:    # 치즈가 있다면   
                cheese += 1         # 치즈 +1
                for d in range(4):
                    ni, nj = i + dr[d], j + dc[d]
                    # 치즈칸에서 4방향 탐색하여 공기층이 있다면 cnt+1
                    if air[ni][nj] == 1:
                        cnt += 1
                # 공기층이 2칸 이상이라면 치즈가 녹음
                if cnt >= 2:
                    paper[i][j] = 0
    # 치즈가 하나도없었다면 반복종료
    if cheese == 0:
        break
    # 아니라면 시간 +1
    else:
        time += 1

print(time)