백준 1113 수영장 만들기 python

문제를 처음 봤을때 BFS 같은 걸 써서 경계를 찾아서 어떻게 해야될거 같은데 기발한 방법이 떠오르지 않았다.
문제 조건을 보니 N, M은 50, 높이값은 1 ~ 9로 범위가 작아서 각 높이마다 하나하나 처리해주는 방법을 썼다.

📜 문제 바로 가기 : 수영장 만들기

제출코드

파이썬

import sys
input = sys.stdin.readline

def find_root(i, j, h):
    stack = [(i, j)]
    visit = [[False] * M for _ in range(N)]
    visit[i][j] = True

    flag = True
    while stack:
        ni, nj = stack.pop()
        for di, dj in delta:
            i, j = ni+di, nj+dj
            if isRange(i, j) == False or visit[i][j] == True:
                continue
            
            if isBoundary(i, j) == True: 
                if arr[i][j] <= h: # 물을 가둘 수 없는 경우
                    flag = False
            elif arr[i][j] == 0: # 물을 가둘 수 없는 경우
                flag = False
                visit[i][j] = True
            elif arr[i][j] <= h:
                visit[i][j] = True
                stack.append((i, j))

    amount = 0

    if flag == True: # 물을 가둘 수 있음. == 물 높이 1 상승    
        for i in range(1, N-1):
            for j in range(1, M-1):
                if visit[i][j] == True:
                    arr[i][j] = h+1
                    amount += 1
    
    else: # 물을 가둘 수 없음.
        for i in range(1, N-1):
            for j in range(1, M-1):
                if visit[i][j] == True:
                    arr[i][j] = 0
    
    return amount


def isBoundary(i, j):
    if (i == 0 or i == N-1) or (j == 0 or j == M-1):
        return True
    return False

def isRange(i, j):
    if 0 <= i < N and 0 <= j < M:
        return True
    return False

delta = [(0,1), (0,-1), (1,0), (-1,0)]
N, M = map(int, input().split())
arr = [list(map(int, input().rstrip())) for _ in range(N)]

ans = 0
for h in range(1, 9):
    for i in range(1, N-1):
        for j in range(1, M-1):
            if arr[i][j] == h:
                ans += find_root(i, j, h)

print(ans)

접근방법

지면의 높이가 1 ~ 9까지 범위가 작은 것을 이용하여 하나하나 보기로 했다.
즉 지면이 x인 지면을 찾아서 그 지면이 큰 값으로 둘러 쌓여 있는지를 확인하고 둘러 쌓여있다면 물양을 +1 해주고 지면을 1 높이는 방법을 사용했다.

물을 가둘 수 없는 경우를 찾는 방법

지면의 높이 h를 기준으로 BFS나 DFS 방식으로 탐색을 하되 경계면에서 한가지 고려해야 한다.
BFS or DFS를 통해 경계면 까지 좌표가 갔다는 것은 높은 지면이 없어서 이어졌다는 뜻이된다.
따라서 경계면의 지면 높이 마저 h보다 작거나 같다면 이번 BFS, DFS 를 통해 방문한 좌표값들은 물은 채울 수 없다는 얘기가 된다.