[Python] BOJ 2573 - 빙산

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

2573번: 빙산

# BFS/DFS + 시뮬레이션 문제이다.

   BFS나 DFS 중 아무거나 선택해서 풀면 되는데, BFS가 편해서 BFS로 풀었다.

   

1. 매 시간마다 m을 돌면서 m[i][j]가 0이 아니고 방문하지 않은 지점이라면 

    iceberg를 1증가시키고 bfs(i, j, visited)를 실행한다.

 

# bfs함수: 상하좌우를 탐색하며 m[nx][ny]가 0이면 diff[(x, y)] += 1을 해줌으로써

                diff 딕셔너리에는 빙하가 녹을 좌표와 녹을 양이 저장된다.

                또, m[nx][ny]가 0이 아니고 방문하지 않은 지점이라면 방문처리를 하고 q에 넣어준다.

                최종적으로 diff 딕셔너리를 return 해준다.

 

2. 매 시간마다 bfs함수를 돌려 d에 저장해주고 d의 좌표들에 해당하는 m[x][y]값을

    max(0, m[x][y] - d[(x, y)])로 갱신해준다. (처음에 그냥 m[x][y] - d[(x, y)]로 했다가 m[x][y]값이

    0 미만으로 내려가는 상황이 생겨서 max함수를 통해 0보다 안내려가도록 설정했다.)

 

3. iceberg가 2이상이면, 빙산이 두 조각 이상으로 분리된 것이므로 time을 출력하고 break

   iceberg가 0이면 끝까지 빙산이 두 조각으로 분리가 안 되었으므로 0 출력하고 break

   그 외의 경우는 time 1 증가시키고 while문을 계속 돌린다.

 

import sys
from collections import defaultdict, deque
input = sys.stdin.readline
N, M = map(int,input().split())
dx, dy = [-1, 1, 0, 0], [0, 0, -1, 1]
m = [list(map(int,input().split())) for _ in range(N)]
q = deque()

def bfs(i, j, visited):
    diff = defaultdict(int)
    q.append((i, j))  
    visited[i][j] = True
    while q:
        x, y = q.popleft()
        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]
            if 0 <= nx < N and 0 <= ny < M:
                if m[nx][ny] == 0:
                    diff[(x, y)] += 1
                elif m[nx][ny] and not visited[nx][ny]:
                    visited[nx][ny] = True
                    q.append((nx, ny))

    return diff

time = 0
while True:
    iceberg = 0
    visited = [[False] * M for _ in range(N)]
    for i in range(N):
        for j in range(M):
            if m[i][j] and not visited[i][j]:
                iceberg += 1
                d = bfs(i, j, visited)
    
    for x, y in d:
        m[x][y] = max(0, m[x][y] - d[(x, y)])
    if iceberg >= 2:
        print(time)
        break
    if iceberg == 0:
        print(0)
        break
    time += 1

(solved.ac 티어: 골드 4)