[99클럽 코테 스터디 4일차 TIL] 백준 2468 안전 영역 Python 깊이/너비 우선 탐색(DFS/BFS)

오늘의 학습 키워드

깊이/너비 우선 탐색(DFS/BFS)

공부한 내용 본인의 언어로 정리하기

문제

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

코드

import sys
sys.setrecursionlimit(100000)

n = int(input())
rain = []
for i in range(n):
    a = list(map(int, input().split()))
    rain.append(a)

dy = [-1, 1, 0, 0]
dx = [0, 0, -1, 1]
result = 0

def dfs(x, y, t):
    visited[y][x] = 1
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if (0 <= nx < n) and (0 <= ny < n) and visited[ny][nx] == 0 and rain[ny][nx] > t:
            dfs(nx, ny, t)

for t in range(max(map(max, rain))):
    visited = [[0] * n for i in range(n)]
    count = 0
    for y in range(n):
        for x in range(n):
            if rain[y][x] > t and visited[y][x] == 0:
                dfs(x, y, t)
                count += 1
    result = max(count, result)

print(result)

 

해당 문제는 전형적인 우선 탐색 문제이다. 우선 dfs 함수를 통해 범위 안에 만족하는 수라면 방문 처리를 하고 재귀형식을 통해 다시 dfs 문을 부르면서 해당 블록과 연결된 블록 또한 연속으로 검사한다. 

for문을 통해 region 에 있는 수 중 가장 큰 수를 정해 0부터 max 값까지 i를 1씩 더해가며 높이 정보를 갱신한다. 이때 count값과 visited 값은 매번 높이가 변할 때 마다 초기화를 진행해야 한다. 이후 각 높이 지역마다 물에 잠기지 않는 영역을 count를 통해 하나씩 세고, 해당 count 값을 기존에 저장되어 있는 result값과 비교하며 지속적 갱신을 통해 안전 영역의 최대 개수를 구한다.

오늘의 회고

오늘의 문제는 전형적인 dfs/bfs 문제였다. 해당 유형은 내가 제일 약한 유형 중 하나인데, 오늘 문제를 풀면서 dfs의 재귀 원리를 다시 한 번 공부할 수 있었다. 특히 visited 랑 count를 초기화 하는 걸 놓쳐 조금 헤메었다. 앞으로는 알고리즘을 조금 더 체계적으로 짜야지..