[골드 1] 백준 1113 - 수영장 만들기 (파이썬)

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

풀이

• 높은 정보가 주어진 N * M 격자판이 존재한다.
• 외곽은 절대 물을 담을 수 없고, 안쪽에 고인 물의 양을 계산해야한다.
• 물은 본의의 높이보다 낮은 곳에 채워질 수 있다.
• 각 칸에 고일 수 있는 물의 양을 계산해서 전체 합을 출력한다.

결국 BFS로 해결해야 한다고 생각된다.

1. 모든 칸을 순회하면 (i, j) 칸에 물 1단계씩 채워보며 시도한다.
2. 채웠을 때 외곽까지 닿을 수 있다면 물은 새기 때문에 그만 둔다.
3. 외곽까지 닿지 않으면 물이 고일 수 있으므로 해당 칸 높이를 올리고 answer += 1을 진행한다.
4. 이 과정을 해당 칸에서 물이 넘칠 때 까지 반복한다.

BFS 탐색으로 물이 새는지 확인하기 위해서 다음과 같이 정의 했다.

while True :
    visit = [[False] * M for _ in range(N)]
    queue = deque()
    queue.append((i, j))
    visit[i][j] = True

    ground = False

현재 위치 (i, j)에서 시작해서 같거나 낮은 곳만 탐색하며, 외곽에 도달하면 ground = True로 변경한다.

그리고 물이 새지 않는 다면 1만큼 채운다.

if ground :
    break
else :
    B[i][j] += 1
    answer += 1

외곽에 도달하지 않았다면 현재 칸에 물을 1만큼 고일 수 있다.

그런데 이 풀이는 모든 칸에 대해 최대 높이만큼 물을 한 칸씩 채워보는 방식이라서 시간복잡도가 O(NMH) 정도로 나올 수 있다.

아마 우선순위 큐 + 다익스트라 방식으로 낮은 곳부터 차오르게 해서 한 번의 BFS로 전체 영역 처리하는 방식이 더 효율적일것 같다.

코드

# 백준 1113 - 수영장 만들기
# 분류 : BFS

from collections import deque

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

dr = [1, -1, 0, 0]
dc = [0, 0, 1, -1]

answer = 0
for i in range(N) :
    for j in range(M) :
        while True :
            visit = [[False] * M for _ in range(N)]
            queue = deque()

            queue.append((i, j))
            visit[i][j] = True

            ground = False
            while len(queue) != 0 : 
                r, c = queue.popleft()

                if r == 0 or r == N - 1 or c == 0 or c == M - 1 :
                    ground = True
                    break
                    
                for k in range(4) :
                    nr, nc = r + dr[k], c + dc[k]
                    if nr < 0 or N <= nr or nc < 0 or M <= nc :
                        continue
                    if B[i][j] < B[nr][nc] :
                        continue
                    if not visit[nr][nc] :
                        queue.append((nr, nc))
                        visit[nr][nc] = True
        
            if ground :
                break
            else :
                B[i][j] += 1
                answer += 1

print(answer)

# 백준 1113 - 수영장 만들기
# 분류 : BFS

import sys
import heapq
from collections import deque

input = sys.stdin.readline

N, M = map(int, input().split())
board = [list(map(int, list(input().strip()))) for _ in range(N)]
visited = [[False]*M for _ in range(N)]

heap = []
# 외곽 테두리 넣기
for i in range(N):
    for j in range(M):
        if i == 0 or i == N-1 or j == 0 or j == M-1:
            heapq.heappush(heap, (board[i][j], i, j))
            visited[i][j] = True

dr = [1, -1, 0, 0]
dc = [0, 0, 1, -1]
answer = 0

while heap:
    h, r, c = heapq.heappop(heap)

    for d in range(4):
        nr = r + dr[d]
        nc = c + dc[d]

        if 0 <= nr < N and 0 <= nc < M and not visited[nr][nc]:
            visited[nr][nc] = True
            if board[nr][nc] < h:
                answer += h - board[nr][nc]
                board[nr][nc] = h
            heapq.heappush(heap, (board[nr][nc], nr, nc))

print(answer)