[백준 BOJ / Python] 1113번 수영장 만들기

문제

주어진 2차원 배열에서 각 칸에 고일 수 있는 물의 양을 계산하는 문제이다. 각 칸의 물 높이는 주변에 있는 벽(높이가 더 큰 칸들)에 의해 제한되며, 물은 낮은 칸을 채워 나가면서 주위 벽에 의해 막히는 곳에만 고일 수 있다.

풀이

• 이 코드의 핵심은 외곽부터 낮은 높이의 칸을 우선 탐색하면서 물을 채워나가는 것이다.
• 먼저, 외곽에 있는 칸들을 힙에 추가하고 높이가 낮은 칸부터 탐색을 시작한다.
• 탐색하면서 주변에 더 낮은 높이의 칸이 있다면, 현재 칸의 높이만큼 물을 채우고 채운 물의 양을 답에 더한다.
• 물 높이와 상관없이 방문하지 않은 칸이라면 방문 처리 후, 현재 높이와 좌표를 힙에 추가하여 계속해서 주변을 탐색한다.
• 이 과정을 통해 최종적으로 고일 수 있는 물의 양을 계산한다.

Python 코드

import sys
input = sys.stdin.readline
import heapq

n, m = map(int,input().split())
pool = [list(map(int,list(input().strip()))) for _ in range(n)]
visited = [[0] * m for _ in range(n)]

def in_range(x,y):
    return 0<=x<n and 0<=y<m

def solution():
    min_heap = []
    answer = 0

    # 외곽만 먼저 추가
    for i in range(n):
        for j in range(m):
            if 1<=i<n-1 and 1<=j<m-1:
                continue
            heapq.heappush(min_heap, (pool[i][j],i,j))
            visited[i][j] = 1

    while min_heap:
        # 외곽의 낮은 칸부터 탐색
        h,x,y = heapq.heappop(min_heap)

        for dx,dy in [(0,1),(0,-1),(1,0),(-1,0)]:
            nx,ny = x+dx, y+dy

            if not in_range(nx,ny):
                continue
            if visited[nx][ny]:
                continue

            # 현재 칸보다 낮은 칸을 발견하면 물을 채움
            if h > pool[nx][ny]:
                answer += h-pool[nx][ny]
                pool[nx][ny] = h

            heapq.heappush(min_heap,(pool[nx][ny],nx,ny))
            visited[nx][ny] = 1

    print(answer)

solution()

 

문제출처

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