[Softeer] 동계 테스트 시점 예측

 

문제

요약

바깥에서부터 유입되는 공기와 두면이 맞닿아 있는 얼음이 녹는데 1초가 걸릴 때,

얼음이 다 녹을 때까지 시간이 얼마나 걸리는가?

 

원본

https://softeer.ai/practice/6281

Softeer - 현대자동차그룹 SW인재확보플랫폼

풀이

바깥에서부터 유입되는 얼음과 2면이 맞닿아 있어야 하는 건데
무작정 2면만 닿아있으면 되는 줄 알고 얼음이 있는 곳에서 면이 닿아 있는지를 판단해서 틀렸다.

문제를! 잘읽자!

 

import sys
from collections import deque
input = sys.stdin.readline

n, m = map(int, input().split())
arr = [list(map(int, input().split())) for _ in range(n)]
d = [(-1, 0), (1, 0), (0, 1), (0, -1)]
answer = 0

while max([max(arr[k]) for k in range(n)]) != 0:
    visited = [[0] * m for _ in range(n)]
    q = deque([(0,0)])
    visited[0][0] = 1

    while q:
        i, j = q.popleft()
        for di, dj in d:        
            ni, nj = i+di, j+dj
            if 0 <= ni < n and 0 <= nj < m:
                if arr[ni][nj]:
                    visited[ni][nj] += 1
                elif visited[ni][nj] == 0:
                    q.append((ni, nj))
                    visited[ni][nj] = 1

    for i in range(n):
        for j in range(m):
            if visited[i][j] >= 2:
                arr[i][j] = 0

    answer += 1
    
print(answer)