[Softeer][level3] 동계 테스트 시점 예측 (python)

https://softeer.ai/practice/info.do?idx=1&eid=411 

Softeer

 

문제

풀이

BFS를 사용하여 탐색

적어도 2번 이상 외부 공기와 접촉한 얼음을 고려해야하므로 얼음을 만났을 때 count해주고 2번 이상 count된 경우 얼음을 녹이는 것으로 해결.

얼음이 아닌데 방문하지 않았던 경우, 주변 탐색을 위해 queue에 추가

 

코드

import sys
from collections import deque

N, M = map(int, input().split())
grid = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]

def BFS() :
    dx = [1, 0, -1, 0]
    dy = [0, -1, 0, 1]
    queue = deque()
    visited = [[0] * M for _ in range(N)]

    # 첫 번째 시작점
    queue.append([0,0])
    visited[0][0] = 1

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

        for i in range(4) :
            nx = x + dx[i]
            ny = y + dy[i]
            if nx < 0 or nx >= M or ny < 0 or ny >= N :
                continue
            if grid[ny][nx] == 1 :      # 얼음인 경우
                visited[ny][nx] += 1
            elif visited[ny][nx] ==  0 :    # 얼음이 아니고 방문하지 않은 경우 queue에 추가
                queue.append([ny, nx])
                visited[ny][nx] = 1
    for i in range(N) :
        for j in range(M) :
            if visited[i][j] >= 2 :     # 적어도 2변 이상 외부 공기와 접촉한 경우
                grid[i][j] = 0          # 얼음 녹음
    
time = 0
# 얼음 다 녹을 때까지 반복
while True :
    if grid.count(grid[0]) == N :   # 종료 조건
        break
    BFS()
    time += 1

print(time)