[BOJ] 2468번 안전영역

[BOJ] 2468번 안전영역 문제

매우 정석적인 그래프 탐색 문제이다.

문제에서 요구하는 것은 물에 잠기는 단계에 따라 최대 안전 영역의 개수를 구하는 것이다. 즉, 모든 지역에서 가장 높은 지역의 숫자까지 높이를 조절해 가며 영역의 개수를 구해야 한다.

이를 위해서는 기존 영역을 구하는 그래프 탐색 스킬에 높이에 따른 영역 개수를 구하는 브루트포스 알고리즘까지 넣으면 된다. 18111번 마인크래프트 문제를 풀 때 사용되는 스킬과 비슷하다고 봐도 무방하다.

import sys
from collections import deque

def bfs(x, y, nh):
    global N
    travel = deque([[x, y]])
    dx, dy = [-1, 1, 0, 0], [0, 0, -1, 1]
    while travel:
        now_x, now_y = travel.popleft()
        if visited[now_y][now_x]:
            continue
        visited[now_y][now_x] = True
        for i in range(4):
            next_x, next_y = now_x+dx[i], now_y+dy[i]
            if 0 <= next_x < N and 0 <= next_y < N and graph[next_y][next_x] >= nh and not visited[next_y][next_x]:
                travel.append([next_x, next_y])

if __name__ == '__main__':
    N = int(sys.stdin.readline().rstrip())
    graph = list()
    height = set()
    for _ in range(N):
        now_list = list(map(int, sys.stdin.readline().rstrip().split()))
        graph.append(now_list)
        height.update(now_list)

    height = list(height)
    ans = 0
    for now_height in height:
        now_cnt = 0
        visited = [[False for _ in range(N)] for _ in range(N)]
        for i in range(N):
            for j in range(N):
                if graph[i][j] >= now_height and not visited[i][j]:
                    bfs(j, i, now_height)
                    now_cnt += 1
        ans = max(ans, now_cnt)

    print(ans)

그래프 탐색 방법은 BFS를 사용하였고, 층마다 안전영역을 계산해야 하므로 visited 배열을 층이 바뀔 때마다 초기화해야 한다.