BOJ-2468 안전 영역

https://www.acmicpc.net/problem/2468

문제 소개

지역의 높이 정보가 주어졌을 때 장마철에 물에 잠기지 않는 안전한 영역의 최대 개수를 구한다.

안전한 영역은 물에 잠기지 않는 지점들이 위, 아래, 오른쪽 혹은 왼쪽으로 인접해 있으며 그 크기가 최대인 영역이다.

문제 풀이

처음에는 dfs로 풀었으나 반복문에 재귀까지 사용한 탓인지 결과로 나온 수행시간이 마음에 들지 않아 방법을 바꾸어 bfs로 풀이하였다.

함수 bfs는 상하좌우의 인접한 좌표를 nx와 ny로 표현하며, 유효한 좌표인 동시에 방문하지 않았고 현재 수위를 나타내는 변수인 level보다 지점의 높이가 높은 경우에만 방문한다.

지역에서 가장 높은 높이를 m이라고 했을 때, level의 범위는 1부터 m - 1까지이다.

각 level에 대한 안전한 영역의 개수를 구하여 cnt_list에 append한 후, 마지막으로 cnt_list의 최대값을 출력한다.

코드

from sys import stdin
from collections import deque
input = lambda: stdin.readline().rstrip()

# 좌, 상, 우, 하 순서
dx = [0, -1, 0, 1]
dy = [-1, 0, 1, 0]


def bfs(x, y):
    queue = deque([(x, y)])
    visited[x][y] = True
    while queue:
        tx, ty = queue.popleft()
        for i in range(4):
            nx = tx + dx[i]
            ny = ty + dy[i]
            if 0 <= nx <= n - 1 and 0 <= ny <= n - 1 and arr[nx][ny] > level and not visited[nx][ny]:
                queue.append((nx, ny))
                visited[nx][ny] = True


n = int(input())
arr = [list(map(int, input().split())) for _ in range(n)]

# level의 범위를 정하기 위한 지역 높이 최대값 찾기
m = 0
for i in arr:
    if max(i) > m:
        m = max(i)

# 모든 지점의 높이가 1일 경우 결과는 1이 된다.
if m == 1:
    print(1)
    exit()

# 각 level에서 bfs를 통한 안전한 영역의 개수 구하기
cnt_list = []
for level in range(1, m):
    visited = [[False] * n for _ in range(n)]
    cnt = 0
    for j in range(n):
        for k in range(n):
            if arr[j][k] > level and not visited[j][k]:
                bfs(j, k)
                cnt += 1
    cnt_list.append(cnt)

# 결과 출력
print(max(cnt_list))