[PS] BOJ 2468 / 안전 영역

Minjun Kim

31 Aug 2025 • 3 min read

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

Thumbnail: Photo by Amy Gatenby (Unsplash)

그래프 탐색을 활용하는 문제입니다. 이런 유형의 문제를 푸는 요령을 Flood-Fill이라고도 합니다.

풀이

아이디어

쌓인 비의 높이를 $H$라 할 때, $H = 1 \dots 100$에 대해 다음을 반복합니다.

전체 격자 그래프를 순회하며, 높이가 $H$보다 크고 기존에 방문하지 않았던 칸을 발견하면 즉시 그래프 탐색을 수행합니다.
그래프 탐색을 수행한 횟수가 현재 비의 높이 $H$에 대한 안전 영역의 개수가 됩니다. 모든 $H$에 대해 최댓값을 찾아줍니다.

그래프 탐색

격자 그래프 상에서 DFS 또는 BFS로 적절히 탐색해주면 됩니다. 이번 구현에서는 BFS를 사용했습니다.

N = int(input())
TILE = [list(map(int, input().split())) for _ in range(N)]
visited = [[False] * N for _ in range(N)]
diff = ((0, 1), (0, -1), (1, 0), (-1, 0)) # (dh, dw)

max_safe_areas = 1 # 최대 안전 영역 수
queue = deque()

def bfs(h, w, rain_height):
    queue.append((h, w))
    visited[h][w] = True
    while queue:
        h, w = queue.popleft()
        for dh, dw in diff:
            nh, nw = h + dh, w + dw
            if 0 <= nh < N and 0 <= nw < N and not visited[nh][nw] and TILE[nh][nw] > rain_height:
                visited[nh][nw] = True
                queue.append((nh, nw))

bfs

Flood-Fill

Flood-Fill은 그래프 탐색을 응용하는 알고리즘으로, 다차원 배열에서 어떤 칸과 연결된 영역을 찾는데 사용됩니다.

Flood-Fill 알고리즘은 다음 과정으로 진행됩니다.

전체 그래프의 각 칸에 대해 다음을 반복합니다:

현재 칸 $(h, w)$에 대해, 기존에 방문하지 않았으며 현재 칸이 조건에 부합한다면 다음을 진행합니다.
1. 현재 칸을 방문 처리합니다.
2. 현재 칸에서 그래프 탐색을 시작합니다.
3. 영역의 개수를 1 증가시킵니다.
그렇지 않은 칸에 대해서는 아무것도 하지 않습니다.

def check(h, w):
    """현재 칸 (h, w)가 탐색 조건에 부합하는지 판단합니다."""
    ...

def flood-fill():
    areas = 0
    # Find all possible entrances
    for h in range(N):
        for w in range(N):
            if not visited[h][w] and check(h, w):
                cnt += 1
                bfs(h, w)
    return areas

Flood-Fill 알고리즘 예시

이번 문제에서는 아래와 같이 구현되었습니다.

def count_safe_areas(rain_height):
    cnt = 0
    # Find all possible entrances
    for h in range(N):
        for w in range(N):
            if not visited[h][w] and TILE[h][w] > rain_height:
                cnt += 1
                bfs(h, w, rain_height)
    return cnt

다익스트라 알고리즘의 구현

전체 코드

from collections import deque
input = open(0).readline
N = int(input())
TILE = [list(map(int, input().split())) for _ in range(N)]
visited = [[False] * N for _ in range(N)]
diff = ((0, 1), (0, -1), (1, 0), (-1, 0)) # (dh, dw)

max_safe_areas = 1 # 최대 안전 영역 수
queue = deque()

def init():
    queue.clear()
    for h in range(N):
        for w in range(N):
            visited[h][w] = False

def bfs(h, w, rain_height):
    queue.append((h, w))
    visited[h][w] = True
    while queue:
        h, w = queue.popleft()
        for dh, dw in diff:
            nh, nw = h + dh, w + dw
            if 0 <= nh < N and 0 <= nw < N and not visited[nh][nw] and TILE[nh][nw] > rain_height:
                visited[nh][nw] = True
                queue.append((nh, nw))

def count_safe_areas(rain_height):
    cnt = 0
    # Find all possible entrances
    for h in range(N):
        for w in range(N):
            if not visited[h][w] and TILE[h][w] > rain_height:
                cnt += 1
                bfs(h, w, rain_height)
    return cnt

for i in range(1, 101):
    init()
    res = count_safe_areas(i)
    if res > max_safe_areas:
        max_safe_areas = res

print(max_safe_areas)

solution.py