[백준][DFS] 99클럽 코테 스터디 4일차 TIL + 안전 영역 (+ RecursionError 핸들링 하기)

오늘의 학습 키워드

DFS, 시뮬레이션

 

오늘의 회고

🌱 오늘의 문제

 

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

(왜 미리보기가 안 불러와질까 🥹)

2차원 배열이 주어지고 각각의 칸에는 지형의 높이 정보를 나타내는 자연수 값이 들어간다.

이 문제에서는 장마철에 특정 높이 이상 비가 와 일부 지형이 물에 잠겼을 때, 물에 잠기지 않은 안전 영역의 최대 개수를 묻고 있다.

여기서 안전 영역은 상하좌우로 인접해 있는 지점들이 최대를 이루는 영역을 말한다.

 

 

🌱 나의 시도

최대 영역에 대한 개수를 세는 문제는 마침 어제 공부한 DFS 문제의 예시와 비슷했다.

그래서 나는 이 문제를 재귀 함수를 이용한 DFS로 구현해보려고 한다.

또한 이 문제에서는 장마철에 오는 강우량의 '높이'에 대해 명시하지 않으므로 모든 케이스에 대해 직접 실행해보아야 한다.

 

1. 강우량 높이 결정

따라서 강우량의 높이로 가능한 케이스를 구해보자.

 

1-1. 최소 강우량

우선 문제에서 "아무 지역도 물에 잠기지 않을 수 있다"고 하였다. 아무 지역도 물에 잠기지 않는 경우는 어떤 케이스가 있을까?

1) 비가 오지 않는 경우가 포함될 것이다. -> height = 0

2) 지형의 높이 중 최소 높이보다 비가 적게 오는 경우 또한 아무 지역도 물에 잠기지 않을 것이다. -> height <= min(height_info)

따라서 지형의 최소 높이부터 고려해주면 된다는 것을 알 수 있다.

 

1-2. 최대 강우량

그렇다면 최대 강우량은 어떻게 설정하면 좋을까?

비가 가장 많이 오는 경우는 섬이 모두 물에 잠기는 경우이다. 따라서 지형의 높이 중 최대 높이까지 고려해주면 된다.

 

1-3. 중간 강우량

추가로, 만약 지형 정보가 극단적으로 1과 100으로만 구성되어 있다면 어떨까? 사이의 2, 3, ..., 99를 고려해주는 것은 무의미하다.

따라서 나는 배열로 제공된 지형 정보의 높이 정보값만을 강우량의 높이 케이스로 활용하였다.

 

 

2. 코드 흐름 작성 및 시간 복잡도 고려하기

 

1. 위에서 구한 강우량의 높이별로 DFS의 알고리즘을 적용한다 -> O(h)

2. DFS 알고리즘은 전체 좌표를 돌면서 일정 높이 이상인 지형에 대하여 DFS 함수를 호출한다. -> O(n^2)

3. 각각의 DFS 함수는 인접 노드에 대해 추가로 DFS 함수를 호출한다. (재귀적으로 동작)

 

재귀적으로 동작하는 것까지 포함하여 결국은 배열 전체를 한 번 순회하므로 O(n^2)이지만,

이 과정을 높이마다 반복하므로 이 알고리즘의 시간 복잡도는 O(h・n^2)으로 고려된다.

이 문제에서 배열의 행, 열의 길이가 최대 100이어서 가능하지만 조금만 더 컸다면 시간 초과로 문제를 풀기 어려웠을 것 같다.

 

import sys
sys.setrecursionlimit(10**6)

# 1. 값 입력 받기
n = int(input())
arr = [list(map(int, input().split())) for _ in range(n)]

# 2. 가능한 높이 옵션 추출
height_info = set(sum(arr, []))
directions = [[-1, 0], [0, -1], [1, 0], [0, 1]]

# 3. dfs 함수 정의
def dfs(x, y, limit, visited):
    # 방문 처리
    visited[x][y] = True 
    # 상하좌우 4방향 확인
    for dx, dy in directions:
        nx, ny = x+dx, y+dy
        # 예외 조건 미리 확인
        if nx>=0 and nx<n and ny>=0 and ny<n:
            if not visited[nx][ny] and arr[x][y] > limit:
                dfs(nx, ny, limit, visited)
    return True


max_answer = 1 # 물에 잠기지 않는 경우

# 4. 높이 옵션 별 DFS 알고리즘 적용
for height in height_info:
    visited = [[False]*n for _ in range(n)]
    answer = 0  
    for i in range(n):
        for j in range(n):
            if arr[i][j]>height and not visited[i][j]:
                if dfs(i, j, height, visited):
                    answer += 1 # 개수 카운팅
    # 높이 옵션 중 최대값 탐색
    max_answer = max(max_answer, answer)

print(max_answer)

 

 

 

🌱 새롭게 알게 된 점

이 코드를 작성하면서 두 번의 고비를 통해 코딩 테스트에 대해 새로이 알게된 점들이 있다.

첫 번째로는 코테 실행 환경에서 재귀 함수의 실행 횟수는 엄격하게 제한된다(1,000번 이하)는 점이다. RecursionError가 발생하기 때문인데, 자세한 내용은 하단에서 설명하겠다.

두 번째는 PyPy는 실행 속도가 빠른 대신 메모리를 많이 사용한다는 것을 알게 되었다. 재귀 함수 허용 범위를 늘려주었더니 메모리 범위가 늘어났는데, 이 때 PyPy로 실행하니 메모리 초과 오류가 발생했다. 이 때는 Python으로 돌려주면 된다.

 

- RecursionError 발생

백준에서는 재귀 함수를 최대 1000번까지만 사용할 수 있게 제한을 걸어두었다.

그래서 내 코드는 RecursionError가 발생하였고, 조건문을 이용하여 필요한 경우에만 함수를 호출하도록 수정하여도 역부족이었다.

우선 임시 방편으로 아래 코드 두 줄을 작성하여 재귀 함수의 허용 범위를 늘려주었다.

import sys
sys.setrecursionlimit(10**6)

 

백준에서는 위 방법 외에도 DFS 대신 BFS 를 사용하는 방법이 있다고 하여 이 부분을 추가로 고민해 보는 중이다.

백준 - Recursion Error

 

 

 

오늘의 후기

우선 DFS를 내가 문제에 적용해봤다는 것이 너무 뿌듯하다. 그런데 동시에 고치고 싶은 부분도 많다.

우선 시간 복잡도가 O(h・n^2)가 나왔는데 더 효율적인 방법은 없을지 궁금하다.

그리고 RecursionError를 해결하기 위하여 현재 구현한 DFS 알고리즘에서 재귀 함수 대신 Stack을 사용하거나, BFS로 방법을 바꾸어 이 문제를 해결할 수 있는지도 궁금하다.

 

아이디어. 메모이제이션 활용하여 이전 연산 결과 활용?

내가 손으로 그려보면서 할 때에 낮은 높이부터 고려해보니, 높이를 높일 때 낮은 정보를 바탕으로 정보를 더해갈 수 있었다.

이처럼 메모이제이션 같은 기법을 이용해서 이전 과정의 연산 결과를 활용할 수 없을지 궁금하다.