[백준][그래프] No.2468_안전 영역 01

 

2468번: 안전 영역

얼핏 보기에는 문제가 쉬워보였으나, 읽을수록 이해가 안 갔다.

2차원 배열로 지역의 높이가 주어지고, 물의 높이는 별도로 주어지지 않는다.

이때 '물에 잠기지 않는 안전한 영역의 최대 개수'를 구하라고...?

그럼 물의 높이가 0일 경우에, 모든 영역이 안전하니까 2차원 배열의 크기가 항상 정답 아닌가...?

라고 이해를 못했다.

그래서 직접 그림을 그려보았다.

 

위의 지역(2차원 배열) 높이 그림은 2468번의 예제 입력을 바탕으로 그렸다.

h는 물의 높이이고, 파란색으로 칠한 부분은 물에 잠긴 부분이다.

문제 예제 출력이 5인 것을 염두하고 그림을 봐보자.

 

잠기지 않은 부분이 이어져있다면, 그것은 하나의 덩어리로 세는 것이었다.

그렇게 완전히 나눠진 부분의 개수를 세는 문제였다.

그래서 높이(h)가 4일 때, 영역이 5개로 최대가 되는 상황이다.

 

알고리즘 분류에는 브루트포스 알고리즘와 그래프 탐색이 있다.

처음 말한 것처럼 물의 높이는 알려주지 않는다.

높이가 1 이상 100 이하라는 조건이 있지만, 주어진 지역 중 가장 높이를 MAX로 찾는 것이 더 빠르다.

이런 높이를 다 조사해야 하기 때문에 브루트포스 알고리즘이 붙었다.

또한 '1012번 유기농 배추'나 '4963번 섬의 개수' 같은 그래프 탐색이 붙었다. 

 

# ---------- Main ----------
N = int(input())
height = [list(map(int, input().split())) for _ in range(N)]
MAX = max(map(max, height))

result = 1

height(지역의 높이)를 입력받고, 가장 높은 부분을 MAX 변수에 저장한다.

결과 변수(result)를 초기화 해주는데 이때 조심해야 한다.

당연히 밑에 작성하는 알고리즘에서 "0보다 언제나 큰 값이 나오겠지"라는 안일한 생각을 했다.

처음에 0으로 초기화하고 '틀렸습니다'를 본 뒤, 문제의 노트를 읽었다.

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

이말은 최소 값이 1이라는 것이다. 초기화 하나를 하더라도 주의하자.

 

# ---------- Main ----------
for level in range(1, MAX):
    isSink = [[0]*N for _ in range(N)]   
     
    cnt = 0
    for row in range(N):
        for col in range(N):
            if height[row][col] > level and not isSink[row][col]:
                cnt += 1
                DFS(row, col, level)
                        
    result = max(result, cnt)
    
print(result)

물의 높이(level)를 1부터 MAX까지 탐색한다.

매 검사마다 잠긴 것을 확인하는 isSink 배열을 생성했다.

모든 2차원 배열의 요소를 확인하면서 DFS를 검사하고 최종적으로 가장 큰 값을 출력한다.

 

코드로 확인해야 할 부분은 잠기지 않은 부분이기 때문에 if문의 조건은 2가지이다.

하나, 현재 높이(height[row][col])가 검사하는 높이(level)보다 높을 것

둘, isSink의 값이 잠긴 상태가 아닐 것

 

# ---------- Function ----------
def DFS(x, y, h):    
    if x < 0 or y < 0 or x >= N or y >= N:
        return False
    
    if height[x][y] > h and isSink[x][y] == 0:
        isSink[x][y] = 1
        DFS(x, y+1, h)
        DFS(x, y-1, h)
        DFS(x+1, y, h)
        DFS(x-1, y, h)
        
        return True
    return False

위와 가장 유사하다고 느낀 문제는 '백준 4963번 섬의 개수' 문제이다.

본인이 위의 문제를 풀었기에 DFS 과정을 참고했다.

 

0보다 작거나, 입력보다 크거나 하는 식의 경우 False를 return한다.

위에서 말했듯 확인하는 부분은 잠기지 않은 부분이다.

따라서 if문에서 height[x][y]가 h보다 크면서, isSink가 잠기지 않아야 한다.

이때 isSink를 1로 바꿔주고 상하좌우의 값들을 확인한다.

 

일반적인 DFS 문제들을 계속 풀었다면, 어느정도 쉽게 풀 수 있는 문제였다.