[DFS/BFS] 백준 #2468 안전 영역 - Python

🗂️ 문제

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

 

💡 접근법

영역의 최대 높이를 구한 뒤 0부터 최대높이까지 모든 경우에 대해 안전한 영역의 수를 센다.

 

이때 안전한 영역의 수를 세기 위해 DFS나 BFS를 통해 지도를 탐색하여 특정 높이보다 해당 영역의 높이가 높다면(maps[nx][ny] > m) 탐색을 계속한다. 그리고 최종적으로 영역의 개수의 최댓값을 출력한다.

 

또한, 상하좌우로 이어진 것을 하나의 영역으로 보기 때문에 BFS를 썼을 경우에 성능을 더 최적화할 수 있다.

 

😎 내 코드

import sys
sys.setrecursionlimit(10**6)

N = int(sys.stdin.readline())

maps = []
max_value = 0
for _ in range(N):
    temp = list(map(int, sys.stdin.readline().split()))

    if max(temp) > max_value:
        max_value = max(temp)
    maps.append(temp)

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

def DFS(x, y, m):
    visited[x][y] = True

    for ax, ay in zip(dx, dy):
        nx = x + ax
        ny = y + ay

        if N > nx >= 0 and N > ny >= 0:
            if maps[nx][ny] > m and not visited[nx][ny]:
                DFS(nx, ny, m)

area_list = []
for m in range(max_value):
    cnt = 0
    visited = [[False] * N for i in range(N)]
    for i in range(N):
        for j in range(N):
            if maps[i][j] > m and not visited[i][j]:
                cnt += 1
                DFS(i, j, m)

    area_list.append(cnt)

print(max(area_list))

 

✅ 정답 확인