백준 2573번(빙산) 파이썬

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

2573번: 빙산

오랜만에 골드 문제를 건드려봤다.

요즘 그래프 관련 문제를 안푼지 오래되서 감 좀 살릴겸 건드려봤는데 조금 어려웠다.

그래도 맞았다고 떠서 다행이였다. 또 답안을 봐야하나 싶었지만... 결국 풀어내긴 했다.

하지만 python3로 맞추고 싶었는데(34%에서 시간초과가 떴다...) pypy3로 맞추게 되었다.

질문게시판에 질문도 올려봤는데 pypy3로 맞춰도 된다는 말만 나오고 코드에 관해 시간초과 부분의 해결방법을 알려주시는 분은 없어서

pypy3로 마무리 하려 한다. 혹시 아시는분은 댓글 남겨 주세요!! 

아래는 풀이 코드이다.(bfs문은 설명이 생략되어 있는데 이유는 문제 자체가 골4 문제이기 때문에 bfs에 대한 어느정도 지식은 안다는 가정하에 주석 설명을 달아 놓아서 일반적은 bfs문은 따로 설명하지 않았습니다!)

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

n,m = map(int,input().split())
graph = []
dy = [0,0,1,-1]
dx = [1,-1,0,0]

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

def bfs(a,b): # 일반적인 bfs 입니다.
    q=deque()
    q.append((a,b))
    visited[a][b]=True
    cnt=1

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

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

            if 0<=nx<n and 0<=ny<m and graph[nx][ny] != 0 and visited[nx][ny] == False:
                visited[nx][ny]=True
                q.append((nx,ny))
                cnt+=1
    return cnt

def check_glacier():# 1년이 지날때 마다 빙하의 높이를 갱신해주는 함수입니다.
    mountain = [[0]*m for _ in range(n)]
    for i in range(n):
        for j in range(m):
            ice = 0
            if graph[i][j] != 0:
                for k in range(4):
                    if graph[i+dx[k]][j+dy[k]] == 0: # 해당위치의 상하좌우에 0이 몇개있는지 검사합니다.
                        ice+=1
                mountain[i][j]=ice # mountain 리스트에 해당위치의 0과 인접한 갯수를 넣어줍니다.
    for i in range(n): # 초기의 graph에서 mountain의 값(주위에 있는 0의 갯수)을 빼줍니다. -> 1년 후의 빙산의 모습이 생깁니다.
        for j in range(m):
            if graph[i][j] - mountain[i][j]>0:
                graph[i][j]-=mountain[i][j]
            else:
                graph[i][j] = 0
    
year = 1 
glacier = []
flag=0
while True:
    glacier = []
    visited = [[False]*m for _ in range(n)]
    check_glacier() # 1년후의 빙하를 계산합니다
    for i in range(n):
        for j in range(m):
            if graph[i][j] != 0 and visited[i][j] == False:
                glacier.append(bfs(i,j)) # 빙하 섬의 갯수를 넣어줍니다
    if len(glacier) == 0:
        break
    if len(glacier) >= 2:
        flag=1
        break
    year+=1

if flag == 1:
    print(year)
else:
    print(0)