[Baekjoon 2573 / Python / 골드4] 빙산

문제

문제

 

DFS, BFS 문제이다. 처음에 DFS로 풀어보려 했지만 도저히 머리를 싸매도 감이 안 와서 다른 풀이를 참고해 BFS로 풀었다. 근데 풀고 나니 별로 어렵게 느껴지지가 않는다. 뭐든 그런 것 같다. 해내기 전엔 어렵고 해내고 나면 당연한 게 되고 말이다.

 

# BFS

from collections import deque

import sys

input = sys.stdin.readline

N, M = map(int, input().split()) # 행, 열

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

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

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

def iceBreaker():

    # 빙산을 녹이고 개수를 세는 작업이 1번의 반복

    # year는 지난 햇수

    for year in range(1, 1000000):

        # 1. 각 빙산을 얼마나 녹여야 할지 계산

        iceSub = [[0] * M for _ in range(N)]

        for x in range(1, N - 1):

            for y in range(1, M - 1):

                if ice[x][y] > 0: # 빙산일 경우

                    # 4방향 바닷물 세기

                    for i in range(4):

                        nx, ny = x + dx[i], y + dy[i]

                       

                        # 바닷물일 경우 녹여야 할 높이 증가

                        if ice[nx][ny] == 0:

                            iceSub[x][y] += 1

       

        # 2. 빙산 녹이기

        for x in range(1, N - 1):

            for y in range(1, M - 1):

                if ice[x][y] > 0: # 빙산일 경우

                    ice[x][y] = max(0, ice[x][y] - iceSub[x][y]) # 녹인다, 최하 0

       

        # 3. BFS로 덩어리 세기

        visited = [[False] * M for _ in range(N)]

        cnt = 0

        for x in range(1, N - 1):

            for y in range(1, M - 1):

                if ice[x][y] > 0 and not visited[x][y]: # 방문하지 않은 빙산일 경우 BFS 진행

                    BFS(x, y, visited)

                    cnt += 1 # BFS 한번 당 덩어리 1개

                    # 2덩어리 이상이라면 즉시 year 리턴

                    if cnt > 1: return year

        # 1덩어리도 없다는 건 2덩어리가 되지 못하고 모두 녹았다는 것

        if cnt == 0: return 0

# BFS로 하나의 빙산 덩어리를 순회하며 방문체크

def BFS(sx, sy, visited):

    queue = deque()

    queue.append([sx, sy])

    visited[sx][sy] = True

    while queue:

        x, y = queue.popleft()

        # 4방향 체크

        for i in range(4):

            nx, ny = x + dx[i], y + dy[i]

            # 방문하지 않은 빙산일 경우 큐에 넣고 방문처리

            if ice[nx][ny] > 0 and not visited[nx][ny]:

                queue.append([nx, ny])

                visited[nx][ny] = True

print(iceBreaker())

 

코드가 좀 길다. 하지만 원리는 매우 단순하다.

문제 해결은 크게 3가지 단계로 나뉘며, BFS 자체는 기본적인 수준으로만 사용된다.

 

1. 모든 좌표를 순회하며 주변 4방향 바닷물 개수를 세서 iceSub 리스트에 따로 저장해두기. 특정 빙산의 높이를 얼마나 줄여야 할지를 저장하는 것이다.

2. 모든 좌표를 순회하며 iceSub에 저장된 값만큼 높이를 줄이기. 단, 최하값은 0이다.

3. 모든 좌표를 순회하며 visited를 사용한 BFS로 방문하지 않은 빙산을 시작점으로 탐색한다. 즉, BFS가 한번 발동한다면 덩어리가 1개인 것이고 2번 발동한다면 2개, 10번 발동한다면 10개인 것이다. 이 값을 cnt에 저장한다.

 

정리하자면 [주변 바닷물 세기] -> [빙산 녹이기] -> [덩어리 세기] 이게 끝이다.

BFS가 사용되긴 했지만 솔직히 빡구현에 더 가깝다는 느낌이 강한 문제였다.

 

 

결과