[알고리즘/파이썬] 백준 2638 - 치즈

문제

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

2638번: 치즈

 

풀이

1. 모서리는 치즈가 없다고 했으니 (0,0)부터 근접한 모든 공기 부분을 BFS로 탐색하여 -1로 변경해준다. (그러면 치즈 내면의 공기 부분은 0으로 남아있을 것) 

2. 2차 for문을 돌면서 arr[i][j] == 1(치즈)일 경우에 근접한 4면 중 공기가 2면 이상인지 확인한다. 두 면 이상이 공기라면 q에 해당 좌표를 넣어둔다.

3. q가 빌 때까지 해당 치즈들을 모두 -1(공기)로 바꿔준다.

 

처음에 이렇게만 했다가 시간초과가 나서 뭘까 어느 부분이 비효율적인거지... 했는데 그냥 중간에 while문을 계속 돌아서 무한루프에 빠져서 그런거였다. 

내가 간과했던 점은 치즈가 공기가 되면서 내면에 있던 0 공기가 -1의 겉 공기가 될 수 있었던건데 그걸 중간에 체크해주지 않았기 때문에 생긴 문제였다. 그래서 while문을 돌면서 1번 과정을 각 단계마다 계속해서 수행할 수 있게끔 변경해주었다!

 

 

코드

from collections import deque
n,m = map(int,input().split())
arr = []
for _ in range(n):
    tmp = list(map(int,input().split()))
    arr.append(tmp)


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

def find_air():
    visited = [[0 for _ in range(m)] for _ in range(n)]
    q = deque()
    q.append((0,0))

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

        for i in range(4):
            nx = x+ dx[i]
            ny = y+ dy[i]

            if nx<0 or ny<0 or nx>=n or ny>=m:
                continue
            if (arr[nx][ny] == 0 or arr[nx][ny] == -1) and visited[nx][ny] == 0:
                arr[nx][ny] = -1
                visited[nx][ny] = 1
                q.append((nx,ny))


def check_melt_spot(x,y):
    air_count = 0
    for i in range(4):
        nx = x+ dx[i]
        ny = y+ dy[i]

        if nx<0 or ny<0 or nx>=n or ny>=m:
            continue
        if arr[nx][ny] == -1:
            air_count += 1

    if air_count >= 2:
        return True
    else:
        return False

time = 0 
while True:
    find_air()
    
    flag = 0
    change_q = deque()



    for i in range(n):
        for j in range(m):
            if arr[i][j] == 1:
                flag = 1
                if check_melt_spot(i,j):
                    change_q.append((i,j))

    
    while change_q:
        x,y = change_q.popleft()
        arr[x][y] = -1
    
    if flag == 0:
        break

    time += 1

print(time)