[소프티어] 동계 테스트 시점 예측 - python (레벨 3)

https://softeer.ai/practice/info.do?eventIdx=1&psProblemId=411 

Softeer

풀이

문제를 보았을때 알수있는 힌트

단순 BFS,DFS 문제에 한가지 조건을 더해서 좀더 어렵게 만들었다. 하지만 문제에 힌트가 있다. 격자 화면의 맨 가장자리에는 얼음이 놓이지 않는 다고한다. 그렇다면 바깥 부분에서 1에 닿는 부분을 체크하며 지워나가면 답을 찾을수있는 문제이다.

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

nx=[0,0,1,-1]
ny=[1,-1,0,0]

n,m = map(int,input().split())
graph=[]
result=0

for i in range(n):
    temp = list(map(int,input().split()))
    graph.append(temp)

while True:
    count=0
    for i in graph:
        count+=sum(i)
    if count==0:
        break
    visited=[[False]*m for _ in range(n)]
    graph_1=[[0]*m for _ in range(n)]
    visited[0][0]=True
    queue = deque()
    queue.append([0,0])
    # print(visited)
    while queue:
        v= queue.popleft()
        # print(v[0],v[1])
        for i in range(4):
            dx=v[0]+nx[i]
            dy=v[1]+ny[i]
            if -1<dx<n and -1<dy<m:
                if graph[dx][dy]==1:
                    graph_1[dx][dy]+=1
                if graph[dx][dy]==0 and visited[dx][dy]==False:
                    visited[dx][dy]=True
                    queue.append([dx,dy])
    for i in range(n):
        for j in range(m):
            if graph_1[i][j]>=2:
                graph[i][j]=0
    
    result+=1
    count=0
    for i in graph:
        count+=sum(i)
    if count==0:
        break
print(result)

https://github.com/dydwkd486/coding_test/blob/main/softeer/동계%20테스트%20시점%20예측.py 

GitHub - dydwkd486/coding_test: 코딩테스트 공부한 내용 정리