[Backjoon] 안전영역

깊이 우선 탐색을 복습해보면서 재미있는 제약조건을 해결하는 문제였다. 나를 포함한 많은 사람들이 비가 안오는 경우를 놓쳐 정답률이 낮은 것 같다. 깊이 우선 탐색을 하면서 한 번 함수가 종료될 때마다 카운트 변수를 하나씩 늘려주면 조건에 해당하는 영역을 셀 수 있다. 

 

import sys

sys.setrecursionlimit(10 ** 6)

def dfs(row, col, limit_height, table, visited):
    if visited[row][col]:
        return

    dx = [0, 0, 1, -1]
    dy = [1, -1, 0, 0]
    visited[row][col] = True
    for idx in range(4):
        row_next = row + dy[idx]
        col_next = col + dx[idx]
        if 0 <= row_next < len(table) and 0 <= col_next < len(table[0]) and table[row_next][col_next] > limit_height:
            dfs(row_next, col_next, limit_height, table, visited)

if __name__ == "__main__":
    size = int(sys.stdin.readline())

    table, max_height = [], 0
    for _ in range(size):
        row = list(map(int, sys.stdin.readline().split(" ")))
        if max(row) > max_height:
            max_height = max(row)
        table.append(row)

    result = 0
    for height in range(max_height, -1, -1):
        now_area = 0
        visited = [[False for _ in range(size)] for _ in range(size)]
        for row in range(size):
            for col in range(size):
                if not visited[row][col] and table[row][col] > height:
                    dfs(row, col, height, table, visited)
                    now_area += 1
        result = max(now_area, result)
        now_area = 0

    print(result)

 

추가적으로 파이썬으로 구현할 때에는 재귀 깊이제한을 해제해줘야한다. 그렇지 않으면 런타임 에러가 발생한다. 재귀 깊이를 sys.setrecursionlimit()으로 지정해주면 문제를 해결할 수 있다.