[백준] 2573 빙산 [Python]

 

 

 

먼저 위의 문제는 그래프 탐색 문제로 dfs, bfs 방법으로 풀 수 있습니다.

 

저는 dfs를 활용해서 문제를 풀어봤습니다. 처음에는 접근하는 방법이 잘못됐는지 얼음의 개수를 판단하는 함수와 dfs 함수를 구현하고나서 연도를 구하는데 한참 헤맸습니다..

 

 

우선 메인부분부터 작성을 하면  아래와 같습니다. 

N,M = map(int,s.readline().split())
    year = 0
    arr = [list(map(int,s.readline().split())) for _ in range(N)]
    
    dx =[0,1,0,-1]
    dy =[1,0,-1,0]
    ice_cnt=0

 

N과 M 입력을 받고 연도를 구할 때 필요한 year와 arr 배열을 이중행렬로 받아서 표시합니다.

 

얼음 주변의 0의 개수를 파악하기 위해 dx, dy를 미리 선언해주고 함수 부분으로 넘어가겠습니다.

 

def dfs(x,y):
    if x<0 or y<0 or x>=N-1 or y>=M-1:
        return
    if arr[x][y]:
        v[x][y]=1
        
    count(x,y)
    for i in range(4):
        nx = x+dx[i]
        ny = y+dy[i]
        
        if not v[nx][ny]:
            if 0<=nx<N and 0<=ny<M and arr[nx][ny]!=0:
                v[nx][ny]=1
                dfs(nx,ny)

이 dfs함수의 if arr[x][y]: 부분은 처음 x,y를 받아온 부분을 if문 없이 받았더니 첫번째 (1,1)이 1로 고정되어서 넣어줬습니다.

dfs가 반복으로 돌면서 해당 (x,y)좌표에 도달했을 때 count함수를 호출해 해당 좌표 근처의 0의 개수를 판단합니다.

 

for문을 통해 4방향을 탐색하고 탐색한 방향에 방문하지않은 (nx,ny)가 있다면 방문처리 후 dfs 재귀함수를 호출합니다.

 

def count(x,y):
    cnt =0
    for i in range(4):
        nx = x+dx[i]
        ny = y+dy[i]
        
        if 0<=nx<N and 0<=ny<M and arr[nx][ny]==0:
            cnt -= 1
    answer[x][y]=cnt

위의 코드는 count함수로 (x,y)좌표에 4방향을 탐색해 arr[nx][ny]==0 (0의개수)를 찾아서 새로운 answer배열에 저장해줍니다.

따로 answer배열에 저장해주는이유는 바로바로 arr배열에 빼주면 다음 arr[nx][ny]의 바다에 접해있는 부분의 갯수가 정확하지 않기 때문에 dfs가 종료되면 한번에 배열을 교체해주기위해 answer에 따로 빼놓았습니다.

 

while True:
        v = [[0]*M for _ in range(N)]
        answer =[[0]*M for _ in range(N)]
        ice_cnt=0
        
        for i in range(1,N):
            for j in range(1,M):
                if not v[i][j] and arr[i][j]>0:
                    dfs(i,j)
                    ice_cnt+=1
           
        if ice_cnt >1:
            break
        elif ice_cnt==0:
            year=0
            break
        
        for i in range(N):
            for j in range(M):
                if answer[i][j]+ arr[i][j] <0:
                    answer[i][j] = 0
                else:
                    answer[i][j] += arr[i][j]

        for i in range(N):
            for j in range(M):
                arr[i][j] = answer[i][j]

        year +=1 
     
                            
    print(year)

 

마지막으로 while문으로  한 사이클 돌 때 마다 v배열(방문체크용) , answer배열(0의개수 카운트누적용)을 초기화시켜주고 arr배열과 answer 배열을 합쳤을때 그 수가 음수가 나오면 0으로 바꿔줍니다. 

 

또한 arr배열을 탐색하면서 아직 방문하지 않고 값이 존재할 때 dfs를 호출할 때 ice_cnt를 카운트해줘 얼음의 덩어리 개수를 판단합니다.

얼음의 덩어리가 2덩이 이상이되면 종료하는 if문에 break를 넣어주고 for 문을 통해서 arr배열과 answer배열을 합치는 과정을 나타냅니다.

 

최종적으로 while안에 한사이클이 돌면 year에 +1해줘서 연도를 계산합니다. 

 

ice_cnt가 1보다 커질때 while문이 종료되고 그 때의 year를 출력해줍니다.  

 

import sys
from sys import stdin as s
sys.setrecursionlimit(10**5)

s = open('input.txt','rt')


def count(x,y):
    cnt =0
    for i in range(4):
        nx = x+dx[i]
        ny = y+dy[i]
        
        if 0<=nx<N and 0<=ny<M and arr[nx][ny]==0:
            cnt -= 1
    answer[x][y]=cnt
       

def dfs(x,y):
    if x<0 or y<0 or x>=N-1 or y>=M-1:
        return
    if arr[x][y]:
        v[x][y]=1
        
    count(x,y)
    for i in range(4):
        nx = x+dx[i]
        ny = y+dy[i]
        
        if not v[nx][ny]:
            if 0<=nx<N and 0<=ny<M and arr[nx][ny]!=0:
                v[nx][ny]=1
                dfs(nx,ny)

            
if __name__=='__main__':
    
    N,M = map(int,s.readline().split())
    year = 0
    arr = [list(map(int,s.readline().split())) for _ in range(N)]
    
    dx =[0,1,0,-1]
    dy =[1,0,-1,0]
    ice_cnt=0
     
    while True:
        v = [[0]*M for _ in range(N)]
        answer =[[0]*M for _ in range(N)]
        ice_cnt=0
        
        for i in range(1,N):
            for j in range(1,M):
                if not v[i][j] and arr[i][j]>0:
                    dfs(i,j)
                    ice_cnt+=1
           
        if ice_cnt >1:
            break
        elif ice_cnt==0:
            year=0
            break
        
        for i in range(N):
            for j in range(M):
                if answer[i][j]+ arr[i][j] <0:
                    answer[i][j] = 0
                else:
                    answer[i][j] += arr[i][j]

        for i in range(N):
            for j in range(M):
                arr[i][j] = answer[i][j]

        year +=1 
     
                            
    print(year)

 

위의 코드는 전체코드인데  처음에 sys.setrecursionlimit(10**5) 부분을 10**9로 제출했는데 메모리 초과가 발생하여 10**5로 바꾸고 제출하니 제출이 완료됐습니다. python3로 채점을 할 시에는 시간초과가 나서 pypy로 제출해보니 제출이 되길래 다음에는 python3로 낼 수 있는 코드를 공부해봐야 겠습니다.