[백준] 2573 빙산 Python

[백준] 2573 빙산 Python

문제를 풀면서 복잡하고 어렵다고 느낀 문제였다. 처음에는 반복문을 써서 노가다?구현을 했는데 시간초과가 나서
최대한 반복문을 돌지 않으려고 빙산 구역을 저장하고, 그 부분만 돌았다.
문제를 구할 때, 중요한 부분은 빙산 bfs를 먼저 하고 빙산을 깎아줘야한다. 문제에 처음 빙산은 한 덩어리라고 제시하여 먼저 빙산을 깎았는데, 다른 사람들의 풀이를 보니 먼저 bfs를 탐색하고 빙산을 깎았다.다른 사람을 풀이를 참고해서 다시 코드를 깔끔하게 짰다.
그리고 맨 가쪽의 부분은 바다이기 때문에 반복문을 고려해서 돌렸다. 조금이라도 반복을 줄이기 위해,,!
원래 내 코드

import sys
from collections import deque
sys.stdin=open("input.txt")
n,m=map(int,input().split())
graph=[]
num=[]

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

for i in range(1,n-1):
    for j in range(1,m-1):
        if graph[i][j]!=0:
            num.append((i,j))

#동서남북
dx=[0,0,1,-1]
dy=[1,-1,0,0]

year=0

def bfs(graph,visited,si,sj):
    q=deque()
    q.append((si,sj))
    visited[si][sj]=True

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

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

            if not visited[nx][ny] and graph[nx][ny]!=0:
                visited[nx][ny]=True
                q.append((nx,ny))

while True:
    new=[[0 for _ in range(m)]for _ in range(n)] #빙하 녹은 후, 상태
    check=0 #다 녹았는지 확인하기 위한 cnt
    result=[] #0이 아닌 값 담을 배열
    #빙하 녹이기
    for i,j in num:
        cnt=0
        for k in range(4):
            nx=i+dx[k]
            ny=j+dy[k]

            if graph[nx][ny]==0:
                cnt+=1
        new[i][j]=max(0,graph[i][j]-cnt)
        if new[i][j]!=0:
            check+=1
            result.append((i,j))

    if check==0: #빙하 이미 다 녹았는 경우, 다 녹을 때 까지 프로그램 종료 못함->두 덩어리 이상으로 분리되지 않았다.
        print(0)
        exit()

    graph=new  #정보 반영해주기

    year += 1

    #빙산 갯수 check
    bcnt=0


    visited=[[False for _ in range(m)]for _ in range(n)] #체크할 배열
    for i,j in result:
        if graph[i][j]!=0 and not visited[i][j]:
            bfs(graph,visited,i,j)
            bcnt+=1

    num=result #정보 반영해주기
    if bcnt>1:
        print(year)
        exit()

수정 코드

import sys
from collections import deque

sys.stdin=open("input.txt")
n,m=map(int,input().split())
graph=[]
for _ in range(n):
    graph.append(list(map(int,input().split())))
#북동남서
dx=[-1,0,1,0]
dy=[0,1,0,-1]

time=0
def bfs(si,sj):
    q=deque()
    q.append((si,sj))
    visited[si][sj]=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:
                # 빙산일 경우
                if visited[nx][ny]==0 and graph[nx][ny]!=0:
                    visited[nx][ny]=1
                    q.append((nx,ny))
                #바다일 경우
                if graph[nx][ny]==0:
                    visited[x][y]+=1 #바다 갯수 저장


while True:
    visited=[[0 for _ in range(m)] for _ in range(n)]
    cnt=0
    #빙산 덩어리 계산 -> 맨 가는 어짜피 바다
    for i in range(1,n-1):
        for j in range(1,m-1):
            if graph[i][j]!=0 and visited[i][j]==0:
                bfs(i,j)
                cnt+=1

    #빙산 깎기
    for i in range(1,n-1):
        for j in range(1,m-1):
            if graph[i][j]!=0 and visited[i][j]!=0:
                graph[i][j]=max(0,graph[i][j]-visited[i][j]+1)

    if cnt>1: #첫번째는 빙산이 한덩어리라서 검사하지 않는다!
        print(time)
        break
    if cnt==0:
        print(0)
        break

    time += 1