Softeer 동계 테스트 시점 예측 (난이도 3)

정답 코드

import sys

N, M = map(int, input().split())
ice = []
for i in range(N):
    ice.append(list(map(int, sys.stdin.readline().split())))


def findOutsideAir(i, j, ice):
    ice[i][j] = -1
    r = [1, -1, 0, 0]
    c = [0, 0, 1, -1]
    queue = [[i, j]]
    while queue:
        cr, cc = queue.pop(0)
        for o in range(4):
            nr = cr + r[o]
            nc = cc + c[o]
            if 0 <= nr < N and 0 <= nc < M and ice[nr][nc] == 0:
                ice[nr][nc] = -1
                queue.append([nr, nc])


def check(i, j, ice):
    r = [1, -1, 0, 0]
    c = [0, 0, 1, -1]
    cnt = 0
    for o in range(4):
        nr = i + r[o]
        nc = j + c[o]
        if 0 <= nr < N and 0 <= nc < M and ice[nr][nc] == -1:
            cnt += 1
    if cnt >= 2:
        return True


time = 0
v = [[False for i in range(M)] for j in range(N)]
while True:
    findOutsideAir(0, 0, ice)
    found = False
    for i in range(N):
        for j in range(M):
            if ice[i][j] == 1:
                result = check(i, j, ice)
                if result:
                    v[i][j] = True
                    found = True
    for i in range(N):
        for j in range(M):
            if v[i][j]:
                ice[i][j] = 0
            if ice[i][j] == -1:
                ice[i][j] = 0
    if found:
        time += 1
    else:
        break
print(time)

알고리즘 유형

BFS

후기

DFS로 풀면 recursion limit가 있기 때문에 BFS로 풀어야 하는 문제.