[Solved] BOJ: 2468 | 안전영역

문제

행과 열의 길이인 n과
지역의 높이 정보를 나타내는 n * n 의 2차원 배열이 입력으로 주어졌을 때,
특정 높이 h 이하의 지역은 모두 물에 잠긴다고 한다.
물에 잠기지 않는 지역들이 상하좌우로 인접해 있고, 그 크기가 최대인 영역인 영역을 안전한 영역이라고 할 때,
특정 높이 h에서 안전한 영역의 개수가 최대가 된다.
안전한 영역의 최대 개수를 구해보자.

입력과 출력

입력

첫째 줄에는 어떤 지역을 나타내는 2차원 배열의 행과 열의 개수 n (2 <= n <= 100)이 입력된다.
둘째 줄부터 n개의 각 줄에는 2차원 배열의 첫 번째 행부터 n번째 행까지 순서대로 한 행씩 높이 정보가 입력된다. (1 <= 높이 <= 100)

출력

안전한 영역의 최대 개수

---

문제 해결 요약

2차원 배열의 (0,0) 좌표부터 한 행씩 접근하면서
물에 잠기지 않은 지역이면 멈춰서 인접한 지역들을 탐색한다 -> DFS, 재귀, 브루트포스

주의사항

1. RecursiveError
2. 무한 재귀
3. 시간초과
4. "아무 지역도 물에 잠기지 않을 수 있다"

코드 설명

import 및 입력받기

지역의 높이 정보를 입력받고,
지역의 높이 종류를 확인하기 위해 집합으로 높이를 저장한다.
-

import sys
sys.setrecursionlimit(10**6)  # RecursiveError 방지
input = sys.stdin.readline

n = int(input())
area = []  # 지역의 높이 정보를 n*n 2차원 배열로 입력받음
height = set([])  # 지역의 높이 종류를 확인하기 위해 집합으로 높이를 저장함
for _ in range(n):
    tmp = list(map(int, input().split()))
    area.append(tmp)
    height |= set(tmp)

❗ RecursiveError

추후 재귀 방식을 사용하기 때문에 RecursiveError가 날 수 있다.(실제로 났다😅)
sys.setrecursionlimit(10**6)로 재귀 limit를 더 크게 지정해줘야한다.

배열 전체 탐색

특정 높이에 대하여 발생하는 안전한 영역의 개수를 모두 확인한다.
확인해 볼 특정 높이는 전에 height 집합의 요소들이다.
-

cnt = 0  # 안전한 영역의 개수
for h in height:
    visited = [[0]*n for _ in range(n)]  # 2차원 배열 초기화
    c_tmp = 0
    for i in range(n):
        for j in range(n):
            if area[i][j] > h and visited[i][j] != 1:
                visited[i][j] = 1
                search(i, j, h)
                c_tmp += 1
    cnt = max(cnt, c_tmp)

• height 집합을 순회하면서
• 특정 높이 h에 대한 안전한 영역의 개수를 c_tmp 변수로 카운트하고,
• 특정 높이 h에 대한 2차원 배열 순회가 모두 끝났으면 cnt와 c_tmp를 비교해 둘 중 최댓값으로 cnt를 갱신해준다.❗ 2차원 배열 초기화[[0]*n for _ in range(n)] 로 해줘야한다.
  [[0]*n]*n] 으로 해주면 [0]*n이 n번 복사되는 형태로 저장된다.

인접한 영역 탐색

DFS 방식으로 인접한 영역에 대해 탐색한다.

-

dxs = [1, 0, -1, 0]
dys = [0, -1, 0, 1]
visited = [[0]*n for _ in range(n)]

def search(y, x, h):
    for dx, dy in zip(dxs, dys):
        if n > y+dy and y+dy >= 0 and n > x+dx and x+dx >= 0:
            if area[y+dy][x+dx] > h and visited[y+dy][x+dx] != 1:
                visited[y+dy][x+dx] = 1
                search(y+dy, x+dx, h)

• 인접한 좌표를 dxs, dys를 zip해주어 접근한다.
• 인접한 좌표가 인덱스 범위를 벗어나는지 확인한다.
• 인접한 좌표가 물에 잠기지 않은 지역이고, 방문한 적이 없다면
• 해당 좌표의 visited 값을 1로 갱신해주어 방문했다는 표시를 해주고
• 그 좌표에 대해 search를 진행한다.

❗ 무한 재귀

search함수 안에 search함수를 호출하는 재귀 방식을 이용하기 때문에
무한 재귀에 빠지지 않도록 visited 변수를 선언해주어
이미 방문했던 지역에 대해서는 탐색을 진행하지 않도록 한다.

반례 체크

반례가 있는지 확인해봐야한다!!!

-

if cnt == 0:
    cnt += 1

❗ 아무 지역도 물에 잠기지 않을 수 있다.

아무 지역도 물에 잠기지 않을 경우 2차원 배열 지역 전체가 하나의 안전한 영역이 되므로
cnt의 값을 1로 갱신해준다.

---

전체 코드