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

물을 채울 수 있는 조건은 다음과 같다.
현재 높이를 A라 할 때

1. 높이 A와 이어지는 영역은 테두리에 닿으면 안 된다. (물이 땅으로 흐름)
2. 상하좌우의 높이가 A보다 작으면 안 된다. (작은 쪽 높이가 테두리로 이어짐)

한번 채워진 영역은 다시 한번 더 채워질 수 있기에 (예제 2번 기준) 높이가 낮은 곳부터 탐색을 해야 한다고 생각했다.

코드의 흐름은 다음과 같다.

1. 찾을 높이를 1 ~ 9까지 정하고 이 높이를 wall이라 한다. (main 함수)
2. wall 값과 동일한 값을 가진 가진 좌표들을 구한다. (findWall 함수)
   1. 만약 테두리와 이어지면 무효
   2. 상하좌우로 탐색한 높이의 최솟값이 wall보다 낮으면 무효
   3. wall 보다 큰 값이 없다면, 해당 영역에 물을 채울 수 없으니 무효
3. 영역을 구하면 상하좌우로 탐색한 높이 중 최솟값으로 갱신한다. (fillWater 함수)

 

from collections import deque
import sys
input = lambda: sys.stdin.readline().strip('\n')

R, C = map(int, input().split())
board = [[] for _ in range(R)]
for i in range(R):
    S = input()
    for s in S:
        board[i].append(ord(s) - ord('0'))
dir = [[1, 0], [-1, 0], [0, 1], [0, -1]]

def main():
    ans = 0
    for i in range(1, 10):
        ans += findWall(i)
    print(ans)

# 테두리는 탐색 X
def findWall(wall):
    ret = 0
    visit = [[False] * C for _ in range(R)]
    for r in range(R):
        if r == 0 or r == R - 1:
            continue
        for c in range(C):
            if c == 0 or c == C - 1:
                continue
            if visit[r][c]:
                continue
            if board[r][c] == wall:
                visit[r][c] = True
                route, minWall = getArea(wall, visit, r, c)
                ret += fillWater(route, minWall, wall)
    return ret

def getArea(wall, visit, hereR, hereC):
    route = [(hereR, hereC)]
    minWall = float("inf")
    error = False
    q = deque([(hereR, hereC)])
    while q:
        hereR, hereC = q.popleft()
        for d in dir:
            thereR, thereC = hereR + d[0], hereC + d[1]
            if thereR < 0 or thereR >= R or thereC < 0 or thereC >= C:
                continue
            there = board[thereR][thereC]
            # 현재 벽과 다른 높이의 벽을 만나면 최솟값 갱신
            if there != wall:
                minWall = min(minWall, there)
                continue
            if visit[thereR][thereC]:
                continue
            # 만약 현재 높이가 테두리를 포함한다면 물을 채울 수 없음
            if thereR == 0 or thereR == R - 1 or thereC == 0 or thereC == C - 1:
                error = True
            visit[thereR][thereC] = True
            route.append((thereR, thereC))
            q.append((thereR, thereC))
    # 현재 높이의 벽이 가장 크거나 가장 낮은 벽이 현재 높이의 벽보다 작거나 테두리를 포함하면 무효
    if minWall == float("inf") or minWall < wall or error:
        return [], 0
    return route, minWall

def fillWater(route, minWall, wall):
    ret = len(route) * (minWall - wall)
    for r, c in route:
        board[r][c] = minWall
    return ret


if __name__ == '__main__':
    main()