[백준/Python] 2468번: 안전 영역

문제

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

2468번: 안전 영역

---

문제 요약

지역의 높이 정보를 가진 크기가 N × N 배열을 입력 받는다.

 

비의 양에 때라 일정 높이 이하의 모든 지점은 물에 잠긴다.

 

첫째 줄에 장마철에 물에 잠기지 않는 안전한 영역의 최대 개수를 출력한다.

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

---

코드

from collections import deque

def bfs(i, j, h):
    check[i][j] = cnt
    q.append((i, j))
    while q:
        i, j = q.popleft()
        for d in range(4):
            ni = i + di[d]
            nj = j + dj[d]
            if 0 <= ni < N and 0 <= nj < N and check[ni][nj] == 0 and arr[ni][nj] > h:
                # ni, nj가 배열 밖을 벗어나지 않고, 방문하지 않았고 안전한 영역이라면
                check[ni][nj] = cnt
                q.append((ni, nj))

N = int(input())

arr = [list(map(int, input().split())) for _ in range(N)]
# 높이 정보를 저장한 2차원 배열

check = [[0] * N for _ in range(N)]
# 탐색을 했는 체크하는 부분

big = 0 # 가장 높은 높이
for i in range(N):
    if big <= max(arr[i]):
        big = max(arr[i])
    
res = -1 # 물에 잠기지 않는 안전한 영역의 최대 개수

di = [0, 0, 1, -1]
dj = [1, -1, 0, 0]

q = deque()

for h in range(big): # h는 물이 차는 높이
    cnt = 1 # 구역 개수
    for x in range(N):
        for y in range(N):
            if check[x][y] == 0 and arr[x][y] > h:
                bfs(x, y, h)
                cnt += 1
    if cnt - 1 > res:
        res = cnt - 1
    check = [[0] * N for _ in range(N)] # check 배열 초기화

if res == -1:
    print(0)
else:
    print(res)

---

코드 설명

1. 높이 정보를 저장한 N × N 2차원 배열을 입력 받는다.

 

2. BFS 탐색 시 이전에 방문했는지를 체크하는 N × N 2차원 배열 check를 생성한다.

+ 초기값은 0 (방문 X)

 

3. 물이 0부터 가장 높은 높이까지 차오를 동안  bfs함수를 통해 BFS 탐색을 진행한다.

 

4. 탐색이 끝날 때마다 안전한 영역의 수 cnt와 이전의 res를 비교하여 갱신한다.

+ check배열의 모든 값을 다시 0으로 초기화

 

5. 반복문이 종료되면 res를 출력한다. (res가 -1,  구역의 수가 0일 때 예외 처리)