[백준] 2573번 빙산 -python 파이썬

문제

 

 

일단 이 문제를 보면 구현해야할 로직이 크게 두가지 이다.

 

 

1.  빙산 깎기

2. 몇 덩어리인지 확인 

 

 

이게 매 해마다 반복되고 종료조건이 충족되면 종료하도록 해주면 된다.

 

먼저 빙산깎기는 이중 for 문 으로 돌면서 값이 0이상인 곳에 들어가면 동서남북의 0의 개수를 구한 후 빙산을 깎아주면 된다

 

 

이때 이중 for문을 돌면서 순차적으로 각 칸의 값을 갱신하는데 이 값이 매해마다 달라지는 것이므로 같은 해에 변경된 값이 다른 좌표의 값에 영향을 줘서는 안된다.

그래서 값을 갱신하기 전에 tmp에 빙산값을 받아서 갱신되지 않은 값을 기준으로 주변 0의 개수를 세도록 해주었다.

 

그런데 빙산의 값은 2차원 배열이므로 단순히 대입이 아니라 deepcopy를 사용해서 저장해주었다.

 

 

그리고 몇 덩어리인지 확인하는 부분은 bfs를 활용해서 0보다 큰 좌표를 만나는 순간 그 좌표와 같은 덩어리인 좌표를 전부 visit처리해서 구해주었다.

 

 

 

 

정답코드

 

from collections import deque
import copy
n,m = map(int,input().split())

ices = [list(map(int, input().split())) for _ in range(n)]


dx = [-1,1,0,0]
dy = [0,0,1,-1]

def bfs(x,y,ices):
    q = deque()
    q.append((x,y))
    visited[x][y] = 1

    while q:
        x,y = q.popleft()
        for k in range(4):
            nx = x + dx[k]
            ny  = y + dy[k]
            #빙산남은곳만 돌기
            if 0<= nx < n and 0<= ny <m and visited[nx][ny] == 0 and ices[nx][ny]>0:
                visited[nx][ny] = 1
                q.append((nx,ny))
    return visited
       
ans = 0


while True:

    #빙산깎기
    tmp = copy.deepcopy(ices)
    for i in range(n):
        for j in range(m):
            #아직 빙산이 있는 곳이라면
            if ices[i][j] > 0:
                minus = 0
                # 얼마나 빼야할지 동서남북 계산 
                for k in range(4):
                    nx = i + dx[k]
                    ny  = j + dy[k]
                    #주변조회할 때 이미 값이 갱신된 것들의 이전값으로 계산하기 위해 tmp사용
                    if 0<= nx < n and 0<= ny <m and tmp[nx][ny] == 0:
                        minus += 1
                if minus >= ices[i][j]:
                    ices[i][j] = 0
                else:
                    ices[i][j] -= minus

    #몇덩어리인지 체크
    check = 0
    visited =[[0] * m for _ in range(n)]
    for i in range(n):
        for j in range(m):
            #빙산이 있으면서 아직 방문한적없는 덩어리일때 
            if ices[i][j] > 0 and visited[i][j] == 0:
                bfs(i,j,ices)
                check += 1
    ans += 1
    #종료조건시 종료
    if check >= 2:
        break
    elif check == 0:
        ans = 0
        break

    

print(ans)