[백준] 1113번 '수영장 만들기' - Python

 

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

1113번: 수영장 만들기

---

문제

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

16661
61116
16661

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

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

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

 

---

코드

from collections import deque
import sys
input = sys.stdin.readline
n, m = map(int, input().rstrip().split())
board = [list(map(int, list(input().rstrip()))) for _ in range(n)]
visited = []
ans = 0

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

def bfs(x, y, h):
    global ans
    q = deque([(x, y)])
    flag = True

    visited[x][y] = True
    cnt = 1
    while q:
        x, y = q.popleft()

        for t in range(4):
            nx = x + dx[t]
            ny = y + dy[t]

            if nx <= -1 or nx >= n or ny <= -1 or ny >= m:
                flag = False
                continue

            if board[nx][ny] <= h and not visited[nx][ny]:
                visited[nx][ny] = True
                q.append((nx, ny))
                cnt += 1

    if flag :
        ans += cnt

for h in range(1, 9):
    visited = [[False] * m for _ in range(n)]
    for i in range(n):
        for j in range(m):
            if board[i][j] <= h and not visited[i][j]:
                bfs(i, j, h)

print(ans)

 

처음에 접근하려고 했던 방식은 가장 자리를 이용해서 안을 물로 채우는 거였는데 도저히 어떻게 할 지 모르겠어서 결국에는 구글링을 해버렸습니다.

 

1부터 8까지의 전체 높이와 n*m 배열 전체를 탐색하여 높이를 1씩 더하면 넘치지 않는지, 넘친다면 탐색을 flag를 False로 만들어 ans에 누적되지 않게 합니다.

 

이게 되는거라고? 라고 생각했는데 신기하네요.. 간단한 방법인데 시간 복잡도 측면에서는 좋지 못하다고 생각됩니다.

파이썬을 너무 오랜만에 써서 좀 힘겹네요;;