[백준/1113] 수영장 만들기 (Python)

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

1113번: 수영장 만들기

 

Difficulty : Gold 1

 

Status : Solved

 

Time : 00:13:02

 

---

 

문제 설명

 

 

지민이는 수영장을 만들려고 한다. 수영장을 만들 곳의 크기는 N*M이고, 각 칸은 직육면체이다. 따라서, 각 칸의 직육면체의 높이가 쓰여 있는 다음과 같은 땅을 생각할 수 있다.

16661
61116
16661

 

이 수영장은 15만큼의 물이 들어있는 수영장을 만들 수 있다. 가운데 3개의 칸에 5만큼 물을 채우면 되기 때문이다.

자 이제 가운데 물을 더 추가했다고 생각하면, 벽(높이가 6인 직육면체)을 넘어서 밖으로 나갈 것이다. 물은 항상 높이가 더 낮은 곳으로만 흐르고, 직육면체 위의 표면에는 물이 없다. 그리고, 땅의 높이는 0이고, 땅은 물을 무한대로 흡수 할 수 있다.

땅의 모양이 주어질 때, 수영장에 물이 얼마만큼 있을 수 있는지 구하는 프로그램을 작성하시오.

 

 

입력 및 출력

 

입력

 

첫째 줄에 N과 M이 주어진다. N과 M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 땅의 높이가 주어진다. 높이는 1보다 크거나 같고, 9보다 작거나 같은 자연수이다.

 

출력

 

첫째 줄에 문제의 정답을 출력한다.

 

입력 예시

 

3 5
16661
61116
16661

 

출력 예시

 

15

 

 

---

 

풀이

 

그래프 탐색을 진행하되, 다음과 같은 규칙을 적용해보자.

 

• 시작 시점의 높이보다 작거나 같은 높이만 방문하도록 한다.
• 만약 더 높은 높이의 좌표를 만난다면, 그 좌표는 벽이다. 벽 좌표의 높이를 저장한다. 모든 벽 좌표에 대해 최소 높이를 저장하는 것이 목표이다.
• 만약 유효 좌표를 벗어났다면, 시작 좌표를 포함한 모든 좌표는 바깥 공간과 맞닿아있다는 것을 의미한다. 따라서 탐색을 중지한다.
• 위에서 탐색을 중지하지 않은 채 모든 방문 가능한 좌표를 방문했다면, 앞서 최소 높이의 벽 좌표를 떠올려보자. 즉 방문했던 모든 좌표들은 최소 벽 높이보다 작으므로, 그 높이의 차만큼 물을 채울 수 있다. 모든 방문 좌표를 최소 벽 높이로 설정하고, 그 차를 최종 결과값에 더해 준다.
• 모든 좌표에 대해 위 탐색을 시행하면 된다.

 

 

풀이 코드

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

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

N, M = map(int, input().split())
map_list = [list(map(int, input().strip())) for _ in range(N)]
result = 0

def bfs(x, y) :
  q = deque([(x, y)])

  init_val = map_list[y][x]
  min_border = 10
  result = set()
  result.add((x, y))
  while q :
    x, y = q.popleft()
    for k in range(4) :
      ax, ay = x + dx[k], y + dy[k]
      if not (-1 < ax < M and -1 < ay < N) :
        return 0, set()
      if map_list[ay][ax] <= init_val and (ax, ay) not in result :
        result.add((ax, ay))
        q.append((ax, ay))
      elif map_list[ay][ax] > init_val :
        min_border = min(min_border, map_list[ay][ax])

  return min_border, result

def fill(val, coord_set) :
  global result
  for x, y in coord_set :
    result += val - map_list[y][x]
    map_list[y][x] = val

for i in range(N) :
  for j in range(M) :
    val, coord_set = bfs(j, i)
    if coord_set :
      fill(val, coord_set)

print(result)

풀이 완료!