파이썬)치즈

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

2636번: 치즈

 

from collections import deque


n, m = map(int, input().split())


arr = []

for i in range(n):
    a = list(map(int, input().split()))
    arr.append(a)


dx = [1, -1, 0, 0]
dy = [0, 0, -1, 1]


time = 0
ans = []


def bfs():
    q = deque()
    cnt = 0
    q.append((0, 0))
    visit[0][0] = True

    while q:
        x, y = q.popleft()

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < n and 0 <= ny < m and visit[nx][ny] == 0:
                if arr[nx][ny] == 0:
                    visit[nx][ny] = True
                    q.append((nx, ny))

                elif arr[nx][ny] == 1:
                    arr[nx][ny] = 0
                    visit[nx][ny] = True
                    cnt += 1

    ans.append(cnt)
    return cnt


while True:
    time += 1

    visit = [[False for _ in range(m)]for _ in range(n)]
    cnt = bfs()

    if cnt == 0:
        break

print(time - 1)
print(ans[-2])

bfs를 이용한 코드이다.

1.arr[0][0]은 무조건 공기니까 0,0부터 시작하여 0인것과 1인것을 찾는다

2/0이라면 q에 append, 1이라면 공기중에 닿은 것이니 해당 숫자를 0으로 바꾼다.

(그러나 q에 append하지 않는다. 왜? => 그것까지 append해버리면 한번에 모든 치즈가 녹아버리기 때문이다)

3. 그 다음 cnt를 + 1 증가시킨다. (녹은 갯수를 세기 위해)

즉, bfs함수에서 cnt는 한시간 동안 녹은 치즈의 개수이고 time은 시간이다.

while True문에서 visit을 초기화 한 후, cnt를 bfs의 리턴값으로 선언한다.

bfs함수로 들어와 0,0부터 0인 것과 1인 것을 살피며1, 2, 3을 수행한다.

4.만약 cnt가 0이라면 치즈가 모두 녹은 것이므로 무한 반복문을 종료한다.

 

---

실수는 한가지다.

bfs를 0으로 해야 치즈의 테두리부터 천천히 녹을텐데 1로 설정해 버린 것이다.

처음 치즈의 모든 위치를 배열에 담고 그 배열로 bfs를 수행했었다.

그렇게 되면 치즈 안에 있는 구멍의 닿은 치즈부분은 녹지 않지만 내가 작성한 방식대로 한다면 녹게 된다.

따라서 정답을 도출할 수가 없다.

그러나 0,0 즉, 가장 테두리의 공기부터 bfs를 수행한다면 이는 치즈의 테두리부터 녹일 수 있게된다.