[til] 알고리즘 백준 안전영역

📘 TIL (Today I Learned)

🧑‍💻 오늘의 문제: 2468번 안전 영역

📌 문제 요약

• 일정한 높이 이하의 지역은 비에 잠긴다고 할 때, 안전 영역이 최대 몇 개인지 구하는 문제이다.

• 각 칸의 높이가 주어지며, 여러 높이를 기준으로 물에 잠기는지 여부를 판단해야 한다.

• 인접한 칸끼리(상하좌우) 하나의 안전 영역으로 묶인다.

🚩 알고리즘 분류

• DFS/BFS

• 브루트포스

🖥️ 내가 작성한 코드 (BFS 풀이 예시)

from collections import deque
import sys
sys.setrecursionlimit(10**6)

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

def bfs(x, y, h, visited, area, n):
    queue = deque()
    queue.append((x, y))
    visited[x][y] = True

    while queue:
        cx, cy = queue.popleft()
        for d in range(4):
            nx = cx + dx[d]
            ny = cy + dy[d]
            if 0 <= nx < n and 0 <= ny < n:
                if not visited[nx][ny] and area[nx][ny] > h:
                    visited[nx][ny] = True
                    queue.append((nx, ny))

n = int(input())
area = [list(map(int, input().split())) for _ in range(n)]
max_height = max(max(row) for row in area)

result = 0
for height in range(0, max_height):
    visited = [[False]*n for _ in range(n)]
    cnt = 0
    for i in range(n):
        for j in range(n):
            if area[i][j] > height and not visited[i][j]:
                bfs(i, j, height, visited, area, n)
                cnt += 1
    result = max(result, cnt)

print(result)

🔎 내 풀이의 핵심 아이디어

• 주어진 모든 높이에 대해서 반복문을 돌며 안전 영역을 탐색했다.

• BFS 탐색을 통해 안전 영역을 하나씩 찾고, 방문 여부를 체크했다.

• 안전 영역의 개수를 매번 계산하여 최대값을 갱신했다.