[BOJ] 백준 2468 안전 영역 / BFS

이미지를 클릭하면 문제 사이트로 이동합니다.

 

 

💭 문제 이해

2차원 배열에 각 원소는 그 지역의 높이를 담고 있다.

물 높이가 증가함에 따라 일부 지역은 잠기게 되고, 잠기지 않은 연속된 지역을 안전영역이라 한다.

물 높이의 변화에 따라 안전영역의 개수도 변하게 되는데, 이 안전영역 개수의 최대값을 구하는 문제이다.

 

2차원 배열의 최대 크기는 100*100으로 전수조사를 해도 10000번 밖에 되지 않는다.

 

1. 현재 전체 영역의 최소 높이~최대 높이 범위 내에서 탐색을 시작한다.

2. 전체 영역에서 (0, 0) 위치부터 출발해서 현재 물 높이 기준보다 높고, 방문한 적 없는 곳을 만나면,

    거기서부터 너비 우선 탐색을 수행하며 방문체크를 한다.

    그리고 현재 물 높이에서의 안전영역 개수를 1 증가시킨다.

3. 모든 영역을 탐색했으면 현재 물 높이 기준 안전영역 개수와 지금까지의 최대 안전영역 개수를 비교해서 최대값으로 갱신한다.

 

 

 

구현 언어: Python

 

from collections import deque


def bfs(t_x, t_y, height):
    queue = deque()
    # 상 하 좌 우
    mx = [-1, 1, 0, 0]
    my = [0, 0, -1, 1]
    # 시작점
    visited[t_x][t_y] = True
    queue.append((t_x, t_y))

    while queue:
        x, y = queue.popleft()
        for k in range(4):
            nx = x + mx[k]
            ny = y + my[k]

            if 0 <= nx < n and 0 <= ny < n:
                if area[nx][ny] > height and not visited[nx][ny]:
                    visited[nx][ny] = True
                    queue.append((nx, ny))


n = int(input())
area = [list(map(int, input().split())) for _ in range(n)]
min_height = min(map(min, area))  # 최소 물높이
max_height = max(map(max, area))  # 최대 물높이
answer = 1

for h in range(min_height, max_height + 1):
    temp_cnt = 0
    visited = [[False] * n for _ in range(n)]  # 방문체크
    for i in range(n):
        for j in range(n):
            if area[i][j] > h and not visited[i][j]:
                bfs(i, j, h)
                temp_cnt += 1
    answer = max(answer, temp_cnt)

print(answer)