[백준 2468] 안전 영역

2468번: 안전 영역

 

알고리즘 : DFS

난이도 : 실버Ⅰ

 

1. 문제요약

• 어떤 장소를 나타내는 2차원 배열이 주어진다. 각 좌표의 숫자는 장소의 해당 좌표에서의 높이를 나타낸다.
• 비가 내리면 일정 높이 이하의 장소가 물에 잠기게 된다. 비의 양에 따라 물에 잠기지 않는 영역의 개수가 달라진다.
• 비의 양에 따른 안전 영역의 개수의 최대값을 출력하는 문제이다.

2. 구현과정

• 일정 영역의 개수를 구하는 DFS 문제인데 비의 양에 따른 모든 경우를 탐색해 보아야 한다는 점이 특이하다.
• 입력을 받으면서 2차원 배열 field를 생성하고, 이와 함께 높이 집합인 heights도 생성한다. 
• dfs함수를 정의한다. dfs(x,y,k)는 xy좌표에서 시작하여 사방을 탐색하는데 좌표의 값이 k보다 큰 경우 이를 0으로 바꿔주는 함수이다. 이는 특정 높이 k보다 큰 경우 하나의 덩어리로 체크하는 것이다.
• height를 높이원소 h마다 순회한다. 우선 visited라는 field의 복사 배열을 만들고 다시 visited 배열을 순회한다. 여기서 visited[i][j]가 h보다 큰 경우 dfs를 수행하여 하나의 덩어리로 체크한다.
• 위 과정에서 하나의 안전영역을 체크한 것이므로 answer을 +1하고, visited를 모두 탐색하면 answerlist에 answer을 추가한다.
• answerlist에서 가장 큰 값이 문제에서 원하는 출력값이 된다. 

3. 파이썬 코드

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

n = int(input())
field = []
height = set()
for _ in range(n):
    tmp = list(map(int, input().split()))
    field.append(tmp)
    height.update(tmp)
    
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]

# dfs 함수 : visited[x][y]에서 시작하여 주변의 k보다 큰 값을 0으로 바꾼다
def dfs(x, y, k):
    stack = [(x, y)]
    while stack:
        x, y = stack.pop()
        visited[x][y] = 0
        for i in range(4):
            newx, newy = x + dx[i], y + dy[i]
            if 0 <= newx < n and 0 <= newy < n and visited[newx][newy] > k:
                stack.append((newx, newy))

answerlist = [1] # 1은 아무지역도 물에 안잠긴 경우를 의미
for h in height:
    answer = 0
    visited = [[x for x in row] for row in field]
    for i in range(n):
        for j in range(n):
            if visited[i][j] > h:
                dfs(i, j, h)
                answer += 1
    answerlist.append(answer)
print(max(answerlist))