[baekjoon] 백준 2468번(파이썬): 안전 영역

문제

2468번: 안전 영역

- 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다.

- 먼저 어떤 지역의 높이 정보를 파악한다.

- 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 안전한 영역이 최대로 몇 개가 만들어 지는 지를 조사하려고 한다.

- 이때, 문제를 간단하게 하기 위하여, 장마철에 내리는 비의 양에 따라 일정한 높이 이하의 모든 지점은 물에 잠긴다고 가정한다.

- 어떤 지역의 높이 정보는 행과 열의 크기가 각각 N인 2차원 배열 형태로 주어지며 배열의 각 원소는 해당 지점의 높이를 표시하는 자연수이다.

- 예를 들어, 다음은 N=5인 지역의 높이 정보이다.

6	8	2	6	2
3	2	3	4	6
6	7	3	3	2
7	2	5	3	6
8	9	5	2	7

- 이제 위와 같은 지역에 많은 비가 내려서 높이가 4 이하인 모든 지점이 물에 잠겼다고 하자.

- 이 경우에 물에 잠기는 지점을 회색으로 표시하면 다음과 같다. 

6	8	2	6	2
3	2	3	4	6
6	7	3	3	2
7	2	5	3	6
8	9	5	2	7

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

- 위의 경우에서 물에 잠기지 않는 안전한 영역은 5개가 된다(꼭짓점으로만 붙어 있는 두 지점은 인접하지 않는다고 취급한다). 

- 또한 위와 같은 지역에서 높이가 6이하인 지점을 모두 잠기게 만드는 많은 비가 내리면 물에 잠기지 않는 안전한 영역은 아래 그림에서와 같이 네 개가 됨을 확인할 수 있다. 

6	8	2	6	2
3	2	3	4	6
6	7	3	3	2
7	2	5	3	6
8	9	5	2	7

- 이와 같이 장마철에 내리는 비의 양에 따라서 물에 잠기지 않는 안전한 영역의 개수는 다르게 된다.

- 위의 예와 같은 지역에서 내리는 비의 양에 따른 모든 경우를 다 조사해 보면 물에 잠기지 않는 안전한 영역의 개수 중에서 최대인 경우는 5임을 알 수 있다. 

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

- 어떤 지역을 나타내는 2차원 배열의 행과 열의 개수를 나타내는 수 N이 입력된다. N은 2 이상 100 이하의 정수이다.

- N개의 각 줄에는 2차원 배열의 첫 번째 행부터 N번째 행까지 순서대로 한 행씩 높이 정보가 입력된다.

- 각 줄에는 각 행의 첫 번째 열부터 N번째 열까지 N개의 높이 정보를 나타내는 자연수가 빈 칸을 사이에 두고 입력된다. 높이는 1이상 100 이하의 정수이다.

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

알고리즘

- dfs 탐색을 통해 문제를 수행한다.

- 비의 양을 모름으로 0부터 건물의 최대 높이까지 반복하여 안전한 영역을 찾는다.

- 반복 과정에서 안전한 영역의 건물이 없다면 반복을 멈추고 안전한 영역의 최대 값을 출력한다.

코드

import sys
sys.setrecursionlimit(10 ** 6)  # 재귀 허용 깊이를 수동으로 늘려주는 코드


# dfs 탐색
def dfs(x, y, k):
    if x <= -1 or x >= n or y <= -1 or y >= n:
        return False

    # 비의 양보다 높은 건물이고 탐색하지 않았으면 탐색
    if graph[x][y] > k and visited[x][y] == False:

        visited[x][y] = True

        # 상/하/좌/우 재귀적으로 탐색
        dfs(x + 1, y, k)
        dfs(x - 1, y, k)
        dfs(x, y + 1, k)
        dfs(x, y - 1, k)

        return True
    return False


n = int(sys.stdin.readline())

# 각 노드가 연결된 정보를 표현
graph = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]
res = [] # 비의 양에 따른 안전한 영역의 리스트

# 비가 건물의 최대 높이까지 내린다고 가정하여 반복한다.
for k in range(101):

    # 탐색 여부
    visited = [[False] * n for _ in range(n)]

    # 안전한 영역의 건물의 수
    cnt = 0
    for i in range(n):
        for j in range(n):
            if dfs(i, j, k):
                cnt += 1

    # 안전한 영역의 건물의 수를 리스트에 추가
    res.append(cnt)

    # 안전한 영역의 건물이 없다면 멈춘다.
    if cnt == 0:
        break

# 안전한 영역의 최대 개수를 출력
print(max(res))

github

GitHub - junjange/CodingTest: 내가 푼 코딩 테스트 문제와 해결법