2636. 치즈

문제

코드

dirs = [(-1, 0), (1, 0), (0, -1), (0, 1)]

def bfs(x, y):
    q = [(x, y)]
    visited[x][y] = 1
    melt = []
    while q:
        i, j = q.pop(0)
        for k in range(4):
            ni, nj = i + dirs[k][0], j + dirs[k][1]
            if 0 <= ni < n and 0 <= nj < m and not visited[ni][nj]:
                visited[ni][nj] = 1
                if arr[ni][nj] == 1:  # 녹일 치즈
                    melt.append((ni, nj))
                else: # 공기(0)이면 계속탐색
                    q.append((ni, nj))
    for mi, mj in melt:
        arr[mi][mj] = 0
    return len(melt)

n, m = map(int, input().split(" "))
arr = []
cheese = 0
for i in range(n):
    temp = list(map(int, input().split(" ")))
    arr.append(temp)
    cheese += sum(temp)

bfsCnt = 0
while True:
    visited = [[0] * m for _ in range(n)]
    bfsCnt += 1
    melted = bfs(0, 0)
    cheese -= melted
    if cheese == 0:
        print(bfsCnt, melted, sep="\n")
        break

풀이

• 치즈의 바깥부분은 bfs, 0으로 접근하여 알아낸다. 0이면 bfs를 통해 이동하고 1이면 치즈이므로 녹일 리스트에 담아둔다.
• 바로 치즈를 녹이지 않는 이유는 0이 되어 현재 탐색하는 bfs가 녹인후 바로 탐색할수도 있기 때문
• len(melt) 하는 이유는 몇개를 녹였는지 정답에 반환해야 하기 때문임
• 계속 바깥에서부터 탐색하며 바깥쪽 치즈를 찾고, 녹이기를 반복하다보면 모든 치즈를 녹였을 때가 오는데 이때 방금 녹인 치즈의 개수와 bfs를 들어간 횟수를반환하면 된다.