백준-2468-안전 영역

문제

안전 영역

풀이

문제조건 해석

장마철에 물에 잠기지 않는 안전 영역의 최댓값 구하기.

안전 영역은 물에 잠기지 않는 영역의 인접한 집합을 말한다.

물의 높이를 1~(건물 높이의 최댓값-1) 로 순회하면서 완전탐색하면 된다.

• 완탐만 하면 되므로 DFS / BFS 상관없다.

알고리즘

완전탐색은 BFS로 구현하였다.

안전 영역의 수는 visited 배열 이용해서 증가시켰다.

코드

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

n = int(input().rstrip())
arr = []
height = 0
for _ in range(n):
    arr.append([int(x) for x in input().rstrip().split()])
    height = max(arr[-1]) # 건물 높이의 최댓값


def bfs(i, j, level):
    queue = deque([(i, j)])
    while queue:
        i, j = queue.pop()
        for di, dj in ((0, -1), (-1, 0), (0, 1), (1, 0)):
            if not (0 <= i+di < n and 0 <= j+dj < n):
                continue
            if arr[i+di][j+dj] > level and not visited[i+di][j+dj]:
                visited[i+di][j+dj] = True
                queue.append((i+di, j+dj))


answer = 1 # 아무데도 안잠기면 안전 영역의 수는 1
for level in range(1, height):
    visited = [[False for _ in range(n)] for __ in range(n)]
    safety = 0
    for i in range(n):
        for j in range(n):
            if not visited[i][j] and arr[i][j] > level:
                safety += 1
                bfs(i, j, level)
    answer = max(answer, safety)
print(answer)

배운점

• 항상 예외 상황 고려하기
• 완탐 문제는 꼭 BFS안써도 된다. 최솟값 구하는 문제나 탐색 깊이를 알아야 할 때는 BFS 써야 한다.