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

🗂️ 문제

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

 

💡 접근법

BFS 알고리즘을 통해 기준 높이보다 지역의 높이가 높아 물에 잠기지 않는 영역의 개수를 구한다.

 

이를 구하기 위해선 BFS 알고리즘을 통해 인접한 지역(상하좌우)을 탐색할 때 방문하지 않았던 위치(not visited[nx][ny])이면서 기준 높이보다 해당 지역의 높이가 높아야 한다(maps[nx][ny] > h).

 

지도에서 최대 지역의 높이를 찾아 최대 높이만큼 반복하여 안전한 영역의 최대 개수를 구한다.

 

😎 내 코드

import sys
from collections import deque

N = int(sys.stdin.readline())
maps = []
max_height = 0

for _ in range(N):
    maps.append(list(map(int, sys.stdin.readline().split())))
    max_height = max(max_height, max(maps[-1]))

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

def BFS(i, j, h):
    queue = deque()
    queue.append((i, j))
    visited[i][j] = True
    while queue:
        x, y = queue.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if -1 < nx < N and -1 < ny < N:
                if not visited[nx][ny] and maps[nx][ny] > h:
                    visited[nx][ny] = True
                    queue.append((nx, ny))     

max_area = 0
for k in range(max_height):
    visited = [[False] * N for _ in range(N)]
    cnt = 0
    for i in range(N):
        for j in range(N):
            if not visited[i][j] and maps[i][j] > k:
                cnt += 1
                BFS(i, j, k)
                
    max_area = max(max_area, cnt)

print(max_area)

 

✅ 정답 확인