[백준 2636][Python] 치즈

문제 바로가기

2636번: 치즈

풀이 시간: 2시간

처음에 잘못 생각해서 치즈 기준으로 bfs를 했다. 다시 푸느라 오래 걸렸다 ㅜㅜ

 

<문제 Logic>

1. 치즈 안에 있는 구멍은 외부 공기와 접하지 않기 때문에 치즈와 바깥공기가 접하고 있는 부분을 찾아내야 한다. 이를 찾아내기 위해 가장자리부분과 인접한 모든 빈 공간을 bfs로 찾는다. 이때 치즈 안에 있는 공간은 당연히 찾아질 수 없다. 이렇게 찾아낸 부분은 visited에 저장한다.

2. visited에는 치즈인 부분(구멍포함)과 바깥부분 이렇게 나뉘게 된다. 바깥공기와 맞닿은 치즈는 녹아 없어지므로 visited[y][x]가 1이면서 주변이 0인 경우를 찾아서 visited[y][x]를 0으로 바꿔준다.

3. visited와 cheese를 & 연산하면 한 시간이 지난 후의 치즈 모습이 나오게 된다.

4. cheese의 모든 원소가 0이 될 때까지 (치즈가 모두 사라질 때까지) 반복한다.

 

 

-전체 코드-

import sys

pos = [[1,0],[-1,0],[0,1],[0,-1]]

def isIn(y, x):
    if(y>=0 and y<N and x >=0 and x<M):
        return True
    return False

def bfs(y, x):
    cheeseDummy = {}
    queue = []
    queue.append((y, x))
    visited[y][x] = 0
    if y not in cheeseDummy.keys():
        cheeseDummy[y] = []
        cheeseDummy[y].append(x)

    while queue:
        curr = queue.pop(0)
        for i in range(4):
            ny = curr[0] + pos[i][0]
            nx = curr[1] + pos[i][1]

            if(isIn(ny, nx) and cheese[ny][nx] == 0 and visited[ny][nx] == 1):
                queue.append((ny, nx))
                visited[ny][nx] = 0


N = 0 #세로
M = 0 #가로

N, M = map(int, input().split())
cheese = [[int(x) for x in input().split()]for y in range(N)]
time = 0
prev_cnt = 0

for i in range(N):
    prev_cnt += cheese[i].count(1)

while True:
    time +=1
    visited = [[1 for x in range(M)]for y in range(N)]
    # cheeseTmp = [[0 for x in range(M)]for y in range(N)]

    for i in range(N):
        if(cheese[i][0] == 0):
            bfs(i, 0)
        if(cheese[i][M-1] == 0):
            bfs(i, M-1)

    for i in range(M):
        if(cheese[0][i] == 0):
            bfs(0, i)
        if(cheese[N-1][i] == 0):
            bfs(N-1, i)

    # print(visited)

    erase = []
    for i in range(N):
        for j in range(M):
            if(cheese[i][j] == 1):
                for k in range(4):
                    ny = i + pos[k][0]
                    nx = j + pos[k][1]
                    if(visited[ny][nx] == 0):
                        erase.append((i, j))
                        break

    for i in range(len(erase)):
        cheese[erase[i][0]][erase[i][1]] = 0

    for i in range(N):
        for j in range(M):
            cheese[i][j] = visited[i][j] and cheese[i][j]

    # print(cheese)

    cnt = 0
    for i in range(N):
        cnt += cheese[i].count(1)
    # print(cnt)

    if cnt == 0:
        break
    
    prev_cnt = cnt

print(time)
print(prev_cnt)