[백준] 2468 - 안전 영역

문제 설명

문제 링크

정글 그래프 탐색 주제에 있었던 문제이다.

해당 문제는 2차원 배열로 특정 지역의 높이가 주어질 때, 비에 잠기지 않는 ‘안전 영역’의 개수를 구하는 문제인데 여기서 까다로운 점은 비의 높이가 주어지지 않는다는 점이었다. 즉, 모든 비의 높이를 고려하여 그 중 최대 안전 영역 개수를 찾아야 하는 것이다.

지역은 N x N 크기의 2차원 배열이 주어지며, 각 위치의 높이가 주어진다.

문제 풀이

N x N 배열에 있는 수 중 최소값을 ‘최소 물 높이, min_water‘로 설정하고, 최대값을 ‘최대 물 높이 max_water‘로 설정한다. 최대 높이만큼 높아지는 순간 안전 영역의 개수는 0개일 것이며, 최소 높이보다 적게 비가 온다면 안전 영역의 개수는 1개일 것이다.

dy와 dx배열, 그리고 visited배열을 사용하여 2차원 배열이 지도 형식으로 주어졌을 때의 bfs탐색을 구현했다.

조건으로는 내가 이동하고자 하는 방향(상하좌우)이 보드 위일 것(0 <= nx < N and 0<= ny < N), 아직 방문하지 않은 영역일 것(not visited[nx][ny]), 그리고 높이가 물의 높이보다 높을 것(land[nx][ny] > height)을 세웠다.

해당 높이일 때의 안전 영역의 개수를 구하고, 반복문을 통해 물의 높이를 올리면서 최대 안전 영역 개수를 저장했다.

코드

import sys
from collections import deque
input = sys.stdin.readline

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

def bfs(x, y, height, visited, land):
    N = len(land)
    queue = deque([(x, y)])
    visited[x][y] = 1

    while queue:
        cx, cy = queue.popleft()
        for i in range(4):
            nx, ny = cx + dx[i], cy + dy[i]
            if 0 <= nx < N and 0<= ny < N and not visited[nx][ny] and land[nx][ny] > height:
                visited[nx][ny] = 1
                queue.append((nx, ny))


if __name__ == "__main__":
    N = int(input())
    land = [list(map(int, input().split())) for _ in range(N)]

    min_water = min(map(min, land))
    max_water = max(map(max, land))
    max_lands = 1

    for height in range(min_water, max_water+1):
        visited = [[0]*N for _ in range(N)]
        safe_lands = 0

        for i in range(N):
            for j in range(N):
                if land[i][j] > height and not visited[i][j]:    
                    bfs(i, j, height, visited, land)
                    safe_lands += 1

        max_lands = max(max_lands, safe_lands)

print(max_lands)