백준 [2573] 빙산 파이썬 - jimoo

오늘은 백준 [2573] 빙산 파이썬 문제를 설명하겠습니다!!!

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

2573번: 빙산

while True: 부분부터 설명하겠다. 이 부분은 코드를 실행시켰을 때 main 부분이라고 생각하면 된다.

 

나는 빙산의 덩어리 갯수를 확인하고 빙산을 녹이는 순서로 코드를 작성했다.

(첫 번째 while문): 빙산 덩어리 갯수확인-> 빙산녹이기

(두 번째 while문): 빙산덩어리 갯수확인-> 빙산녹이기라고 생각하면 된다.

따라서 while 문이 한 번 반복되면 빙산이 한 번 녹았으니까 year을 증가해주도록 해야한다.

 

temp는 빙산의 높이 배열이 저장된 matrix를 copy한 배열이다.

copy한 이유는 matrix에서 바로 빙산을 녹이게 하는 방법은 문제가 되기 때문이다.

예를들어 (1,1) 좌표에 있는 2를 먼저 녹이면 0으로 바뀌게 된다.

그 이후에 (1,2) 좌표에 있는 4가 빙산을 녹이기 위해 상하좌우를 비교하는 경우,

빙산이 녹아 0으로 바뀐 (1,1) 좌표의 0도 붙어있는 0으로 판단하게된다.

따라서 (1,2) 좌표의 빙산이 녹았을 때 2가아닌 1로 도출되게 된다.

이 문제를 방지하고자 matrix에 원래 빙산의 높이를 보존하고 temp에 녹은 빙산의 결과를 저장하도록 한다. 

check 배열은 빙산이 몇 개의 덩어리로 이루어져 있는지 탐색할 때 사용하는 배열로 한 번 탐색한 빙산을 다시 반복하여 탐색하지 않도록 해준다.

초기에는 n*m 크기의 배열에 0으로 초기화시키고 탐색을 했을 때 1로 변경시킨다. 

 

다음 for i in range(1,n-1): 코드는 빙산이 몇 덩어리로 이루어져 있는지 탐색하고 빙산을 녹이는 코드이다.

배열의 첫 번째 행과 열, 마지막 행과 열은 항상 0 으로 이루어져 있기 때문에 빙산을 녹이는 것과 덩어리 탐색을 할 필요가 없기 때문에 range(1,n-1)로 설정하였다.

 

if matrix[i][j] > 0 and not check[i][j]: 는 빙산의 높이가 0 이상이고 탐색을 하지 않은 좌표일 때 bfs 코드를 실행하도록 하는 조건문이다. 

bfs를 실행한 후 빙산의 덩어리 수(count)를 증가시켜주고 만약 빙산의 덩어리가 2보다 크거나 같다면 year을 출력하고 sys.exit() 로 모든 코드를 중단하도록 한다. 

 

if count==0: 

이 경우는 빙산이 모두 녹아서 두덩이 이상으로 분리되지 않았을 경우 print(0)을 해주는 경우이다. 

빙산이 모두 녹았을 경우에는 if matrix[i][j] > 0 and not check[i][j]: 의 조건을 만족하지 않으므로 bfs함수를 실행할 수 없기때문에 결론적으로 count 되지 않는다.

 

마지막으로 bfs 함수에 대해 설명하도록 하겠다.

            if matrix[nx][ny]!=0 and not check[nx][ny]:
                check[nx][ny] =1
                queue.append((nx,ny))

이 부분은 matrix의 상하좌우 값이 0이아니고 탐색을 하지 않았을 경우 queue에 append 해주는 코드로 빙산의 덩어리 수를 확인할 때 필요한 코드이다.

 

            if matrix[nx][ny] ==0:
                if temp[x][y] == 0:
                    continue
                temp[x][y] -= 1

이 부분은 상하좌우의 값이 0 인경우 matrix를 복사한 temp의 배열의 값을 감소시켜주는 것으로 빙산을 녹이는 코드이다.

if temp[x][y]==0 일때 continue를 해줬는데, 이는 빙산이 모두 녹아 0 으로 바뀐 경우 감소를 시켜주면 마이너스 값이 도출되기 때문에 작성하였다.

 

import sys
from sys import stdin
from collections import deque
import copy

n, m = map(int, stdin.readline().split())
matrix = []
for i in range(n):
    data = list(map(int, input().split()))
    matrix.append(data)
    
dx = [0,0,1,-1]
dy = [1,-1,0,0]

def bfs(x,y):
    queue = [(x, y)]
    check[x][y] = 1 
    queue = deque(queue)
    while queue:
        x,y = queue.popleft()
        for i in range(4):
            nx = x-dx[i]
            ny = y-dy[i]
            if nx<0 or nx>=n or ny<0 or ny>=m:
                continue
            if matrix[nx][ny]!=0 and not check[nx][ny]:
                check[nx][ny] =1
                queue.append((nx,ny))
                
            if matrix[nx][ny] ==0:
                if temp[x][y] == 0:
                    continue
                temp[x][y] -= 1

year=0
while True:
    temp = copy.deepcopy(matrix)
    
    check = [[0] * (m+1) for _ in range(n+1)]
    count=0
    for i in range(1,n-1):
        for j in range(1, m-1):
            if matrix[i][j] > 0 and not check[i][j]:
                bfs(i,j)
                count+=1
                if count >=2:
                    print(year)
                    sys.exit()
    if count==0:
        print(0)
        sys.exit()
    
    matrix = temp
                
    year += 1

 

잘못된 점이 있거나 질문이 있으면 댓글을 달아주세요!!!!!!