🗂️ 문제
링크: 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)
✅ 정답 확인
'Algorithm > Baekjoon' 카테고리의 다른 글
[DP] 백준 #1699 제곱수의 합 - Python (0) | 2024.07.25 |
---|---|
[DP] 백준 #11727 2×n 타일링 2 - Python (0) | 2024.07.25 |
[BFS] 백준 #7562 나이트의 이동 - Python (0) | 2024.05.26 |
[큐] 백준 #1966 프린터 큐 - Python (0) | 2024.05.26 |
[DFS] 백준 #2667 단지번호붙이기 - Python (0) | 2024.05.18 |