백준 2573 빙산 파이썬 (DFS)

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

2573번: 빙산

전형적인 DFS방법으로 풀 수 있는 방법이다 0이 아닌곳을 발견하면 상하좌우로 0의 개수를 찾고 빼주면 되기 때문이다.

이때 한가지 주의 할점은 빼준 곳이 0이 되서 바로 옆자리가 0을 한번 더 카운트 하는 경우만 조심해주면 된다.(빙산은 하루를 기준으로 녹기때문에 같이 녹는다. 예제 그럼에서 처음 2가 0이 되는데 바로 옆에 있는 4가 2가 되는것을 보면 알 수 있다.)

해결 방법으로 dfs에 조건 하나를 더 추가해 줬다. 

또한 영역을 세는 작업을 할때 변경된 배열을 deepcopy해 DFS를 돌리면서 0이 아닌곳을 0으로 다 바꿔줘 영역을 나누는 방법을 썼는데,  이게 하루에 한번씩 deepcopy하다보니 deepcopy부분이 시간을 많이 잡아 먹어 시간초과가 나왔다.

 

그래서 평소와 달리 방문체크 배열을 사용해 영역을 나눴더니 AC를 받았다.

아래는 AC받은 코드이다.

import sys
sys.setrecursionlimit(10**5)
def dfs(i,j):#2가지 경우로 나뉘는걸 체크해주기 위한 함수.
    for k in range(4):
        nx = dx[k]+i
        ny = dy[k]+j
        if 0<=nx<n and 0<=ny<m and vist[nx][ny]:
            vist[nx][ny]=False
            if s[nx][ny]!=0:
                dfs(nx,ny)
            

input = sys.stdin.readline
n,m = map(int,input().split())
s=[list(map(int,input().split())) for _ in range(n)]
dx = [1,-1,0,0]
dy = [0,0,1,-1]
vist = [[False]*m for _ in range(n)]#방문 체크
t = 0

while True:
    t+=1
    for i in range(n):#빙하를 녹이는 함수
        for j in range(m):
            if s[i][j]!=0:
                vist[i][j] = True #앞서 말한 경우를 방지해주기 위한 작업
                c=s[i][j]
                for k in range(4):
                    nx = dx[k]+i
                    ny = dy[k]+j
                    if 0<=nx<n and 0<=ny<m and not vist[nx][ny]:
                        if s[nx][ny]==0:
                            c-=1
                            if c==0:#음수가 되면 안 되니 dfs작업을 멈춰준다.
                                break
                s[i][j]=c#녹은 빙하를 저장해줌
                
    ch=0#영역의 개수
    for i in range(n):
        for j in range(m):#방문체크 배열을 재사용하기 위해 True->False로 다 고쳐준다.
            if s[i][j]!=0 and vist[i][j]:
                dfs(i,j)#영역을 체크한다.
                ch+=1
            elif s[i][j]==0 and vist[i][j]:
                vist[i][j]=False
                
    if ch>=2:#영역이 2개 이상으로 나뉜경우니 출력해주고 반복문을 탈출한다.
        print(t)
        break
    elif ch==0:#한번에 녹았다는 의미이므로 0을 출력해주고 반복문을 탈출한다.
        print(0)
        break