백준: 2468 안전 영역

문제

2468번: 안전 영역

 

문제 풀이

 이전에 다룬 단지번호붙이기, 섬의 개수와 유사한 문제이다. 다른 점이 있다면 비가 오는 양에 따라 침수되는 지역이 달라지며, 그로 인해 안전 영역의 개수가 변동된다는 것이다. 문제를 풀기 위해서는 BFS로 탐색을 하되, 높이가 가장 낮은 곳이 침수될 때부터, 가장 높은 곳이 침수될 때까지 BFS를 탐색하여 영역의 개수를 구하고 최대 값을 반환하면 된다.

 

 

• 3중 반복문을 통해 BFS를 호출한다.
  • 첫 번째 반복문 : 가장 낮은 높이 ~ 가장 높은 높이
  • 두 번째 반복문 : 행을 선택하는 i
  • 세 번째 반복문 : 열을 선택하는 j
    • BFS를 호출할 때, 현재 침수되는 높이보다 큰 것을 탐색한다.

위의 그림의 경우 예제 입력에서 높이 2가 침수될 경우이다. 침수되는 곳 이외의 나머지 부분은 한 영역으로 연결되어 있므로, 높이 2가 침수될 때 안전 영역의 수는 1개이다.

 

 

코드

from sys import stdin
from collections import deque


def visitable(x, y, height):
    return 0 <= x < n and 0 <= y < n and graph[x][y] > height


def bfs(start, height):
    dirs = ((0, 1), (0, -1), (1, 0), (-1, 0))
    q = deque([start])

    while q:
        x, y = q.popleft()
        for dx, dy in dirs:
            next_x, next_y = x + dx, y + dy

            if visitable(next_x, next_y, height) and not visited[next_x][next_y]:
                q.append([next_x, next_y])
                visited[next_x][next_y] = True

    return 1

if __name__ == "__main__":
    n = int(stdin.readline())
    graph = [list(map(int, stdin.readline().split())) for _ in range(n)]
    answer = 1

    for cur_height in range(min(min(graph)), max(max(graph))):
        cnt = 0
        visited = [[False] * n for _ in range(n)]
        for i in range(n):
            for j in range(n):
                if not visited[i][j] and graph[i][j] > cur_height:
                    cnt += bfs([i, j], cur_height)
        answer = max(answer, cnt)
    print(answer)

 테스트 케이스 중에 물에 잠기지 않는 케이스(채점 중 약 95%쯤)인 [[1, 1], [1, 1]]을 입력하면 1을 반환하여야 하는데, 0을 반환한다. 즉 모든 높이가 같은 경우, BFS를 호출하지 않고 최소 안전 영역은 1이기에 answer를 1로 초기화하여 이를 해결하였다.