[BOJ] 2636. 치즈

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

2636번: 치즈

 

 

1. 해결방법

시뮬레이션 BFS 문제이다. 능력 부족으로 3시간 정도 걸렸다,,,,,,

주의해야될 점은 치즈의 겉 부분만 녹아서 없어진다는 부분이다. 본인도 어떻게 로직을 구성할까 고민을 두시간 이상 했다.

시작은 (0, 0)에서 큐에 append하면서 시작한다.
q가 없어질 때까지 while문을 반복한다.
maps에서 인덱스 값이 0에서 0인 위치를 if문으로 판별해서 q에 append한다. 여기서 방문 기록을 해주어야 지나갔던 위치를 다시 재방문하는 예외가 발생하지 않는다.
만약 0에서 1로 이동했다면 (겉 치즈에 도착을 했다면) q에 append하지 않고, 인덱스 값이 1을 0으로 갱신해준 다음 count를 +1해준다. 
count는 인덱스 값이 0에서 1로 변하는 시점에서 공기에서 겉 치즈로 이동했다는 의미로 해석할 수 있으므로, 공기에 녹을 겉 치즈가 몇 개인지 카운팅해줄 수 있는 변수이다.

q가 비었다면 while문은 종료하고 answer 리스트에 count를 append한다. 

여기까지가 1시간의 과정이다.

위의 과정을 while문으로 한번 더 덮어주고 count가 0이 될때까지 반복한다. (count가 0이면 더이상 치즈가 없다는 의미이다)

 

 

2. 정답코드

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

# input
n, m = map(int, input().split())
maps = [list(map(int, input().split())) for _ in range(n)]

# main
dy, dx = (0, 1, 0, -1), (1, 0, -1, 0)
answer = []

while True:
    chk = [[False] * m for _ in range(n)]
    q = deque()
    q.append((0, 0))
    chk[0][0] = True
    count = 0

    # 1시간씩 반복
    while q:
        ey, ex = q.popleft()
        for i in range(4):
            ny, nx = ey + dy[i], ex + dx[i]
            if 0 <= ny < n and 0 <= nx < m:
                # 치즈가 아닌 공기라면 큐에 삽입
                if maps[ny][nx] == 0 and chk[ny][nx] == False:
                    chk[ny][nx] = True
                    q.append((ny, nx))

                # 공기에서 겉 치즈를 발견했을 경우,
                elif maps[ny][nx] == 1:
                    maps[ny][nx] = 0
                    chk[ny][nx] = True
                    count += 1

    answer.append(count)

    if count == 0:
        break

print(len(answer) -1)
print(answer[-2])