[백준/Python] 2573번: 빙산

'DFS+BFS 필수 문제' 문제집 문제집을 푸는 도중 이번 문제는 

조그만 두 문제를 푸는 흥미로운 느낌이어서 가져와봤어요.

빙산 (출처: 네이버 포스트)

 

-문제

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

2573번: 빙산

 

-두개의 작은 문제

1): 1년이 지날 때마다 빙산의 높이가 어떻게 변하는지 확인하라

2): 빙산의 변화에 따라, 빙산이 몇개의 토막으로 나뉘는지 체크하라

3): 계속 반복하여 조건(빙산이 두조각으로 쪼개지거나, 한조각인채 가라앉거나)을 충족하는 시점에 중단하라

 

1) update 함수

모든 위치를 기억해둔 이중 리스트 loc의 값들을 조사하며 그 값이 양수이면 주변의 0보다 작은 값을 카운트하여 업데이트.

 

    주의해야 할 점:

예제의 경우 1년이 지났을 때, loc[1][1]이 0이 되는데 이에 의해 loc[1][2]이 update함수 안에서, 주변에 바다가 2 곳(loc[0][2], loc[1][1])이 있다고 판단할 수 있어요.

 

그래서 저는 시작으로부터 몇년이 지났는지를 세는 trial 변수의 값을 이용해서 해당 trial에 빙산의 높이가 0보다 작아지면 해당 위치에 -(trial)을 선언하도록 했어요.

그리고 각 빙산들이 주변이 바다인지를 판단할 때에는

if -1*trial < loc[new_y][new_x] <= 0:

해당 조건문을 거쳐가도록 해서 이번 trial에 빙산이 0 이하가 되었을 때에는 포함이 되지 않도록 했어요.

 

 

2): bfs 이용

여느 다른 bfs 문제와 같이 0보다 큰 값을 갖는 좌표에 대해 같이 묶여 있는 다른 빙산들을 함께 조사하는데에 bfs를 사용해요.

그리고 방문한 곳도 제외를 해서 연산량도 불필요하게 늘리지 않고 오류도 없애요

 

3) 반복문으로 

trial을 점점 증가시키며 bfs 함수에서 도출되는 빙산 조각수에 주목해 반복을 계속할지 중단할지 판단해요.

 

-소스코드

import sys
input = sys.stdin.readline
from collections import deque

h, w = map(int, input().split())
loc =[list(map(int, input().split())) for _ in range(h)]

x_axis = [1, -1, 0, 0]
y_axis = [0, 0, 1, -1]
def update(x, y, trial):
    global x_axis, y_axis
    cnt = 0
    for i in range(4):
        new_x = x + x_axis[i]
        new_y = y + y_axis[i]
        if 0<=new_x<w and 0<= new_y <h:
            if -1*trial < loc[new_y][new_x] <= 0:
                cnt += 1
    loc[y][x] -= cnt
    if loc[y][x] <= 0:
        loc[y][x] = -1 * trial


def islands(x, y):
    global x_axis, y_axis, visited
    coor = deque([(x, y)])
    visited[y][x] = 1
    
    while coor:
        a = deque.popleft(coor)
        for i in range(4):
            new_x = a[0] + x_axis[i]
            new_y = a[1] + y_axis[i]
            if 0<=new_x<w and 0<= new_y <h:
                if loc[new_y][new_x] >0 and visited[new_y][new_x] == 0:
                    coor.append((new_x, new_y))
                    visited[new_y][new_x] = 1

trial = 0                    
while True:
    trial += 1
    for i in range(h):
        for j in range(w):
            if loc[i][j] >0:
                update(j, i, trial)
    
    num = 0
    visited = [[0] * w for _ in range(h)]
    for a in range(h):
        for b in range(w):
            if loc[a][b] >0 and visited[a][b] == 0:
                islands(b, a)
                num += 1
                if num >= 2:
                    print(trial)
                    quit()
            if loc[a][b] <= 0:
                visited[a][b] = -1
                
    if max(map(max, visited)) <= 0:
        print(0)
        quit()