python 백준 수영장 만들기

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

로직

• 구현, dfs
• 땅의 높이가 1~9사이의 값이므로 각 경우에 물을 얼마나 담을 수 있는 지 확인
  • for h in range(1,10)
  • 지금 생각해보니 range(2,10)이 맞는 것 같다
• 물의 높이가 h일때 물에 잠기는 구역 확인(h보다 낮은 구역)
• 물에 잠기는 구역 중에서 물이 바깥으로 넘치는 구역을 체크
• temp를 R*C 2중배열에 0~2의 값을 할당
  • 0은 그 구역의 땅이 물의 높이보다 높거나 같다
  • 1은 그 구역의 땅이 물의 높이보다 낮다
  • 2는 방문 체크를 위해 사용하는 값, 1인 구역을 탐색 완료시 2로 변경

def solution(R:int,C:int,arr:list[list[int]])->int:
    dr,dc = (0,0,-1,1),(1,-1,0,0)
    total = 0
    for h in range(1,10):
        temp = [[0]*C for _ in range(R)]
        cnt = 0
        for r in range(R):
            for c in range(C):
                if arr[r][c]<h:
                    temp[r][c] = 1
                    cnt += 1
        ls = []
        # 밖으로 흐르는 것 확인
        for r in range(R):
            if temp[r][0] == 1:
                ls.append((r,0))
                temp[r][0] = 2
            if temp[r][C-1] == 1:
                ls.append((r,C-1))
                temp[r][C-1] = 2
        for c in range(C):
            if temp[0][c] == 1:
                ls.append((0,c))
                temp[0][c] = 2
            if temp[R-1][c] == 1:
                ls.append((R-1,c))
                temp[R-1][c] = 2
        while ls:
            cnt -= 1
            r,c = ls.pop()
            for d in range(4):
                nr,nc = r+dr[d], c+dc[d]
                if not (0<=nr<R and 0<=nc<C) or temp[nr][nc] != 1:continue
                temp[nr][nc] = 2
                ls.append((nr,nc))
        total += cnt
    return total

N,M = map(int,input().split())
arr = [list(map(int,input())) for _ in range(N)]
ans = solution(N,M,arr)
print(ans)