[백준 2468번] 안전 영역

from collections import deque

# 2차원 배열의 행과 열 개수
n = int(input())

# 지역 높이 정보(2차원 배열)
area = []
visited = [[False]*n for _ in range(n)]

count_list = []

solution = 0

for _ in range(n):
  area.append(list(map(int,input().split())))

max_value = max(map(max,area))

def bfs(x,y,value):

  if visited[x][y] or (area[x][y]-value) <= 0:
    return False
  
  visited[x][y] = True

  queue = deque([(x,y)])

  while queue:

    v = queue.popleft()

    nx = [-1,1,0,0]
    ny = [0,0,-1,1]

    for i in range(4):
      temp_x = v[0] + nx[i]
      temp_y = v[1] + ny[i]

      if temp_x >= 0 and temp_x < n and temp_y >= 0 and temp_y < n:
        if (area[temp_x][temp_y] - value) > 0 and not visited[temp_x][temp_y]:
          queue.append((temp_x,temp_y))
          visited[temp_x][temp_y] = True

  return True

for i in range(max_value+1):

    count = 0

    for j in range(n):
      for k in range(n):
        if bfs(j,k,i):
          count += 1

    count_list.append(count)

    visited = [[False]*n for _ in range(n)]
  

print(max(count_list))

이번 문제는 물에 잠기는 높이에 따라 영역이 나눠지는 개수를 카운팅하여 최대 값을 구하는 문제이다.

 

문제에서 요구하는 바는 결국 DFS나 BFS 중에 하나를 선택하여 상황에 맞게 영역의 개수를 구하는 것인데, 잠기는 물의 깊이(value)에 따라 나눠지는 영역을 저장하는 과정이 조금 번거로웠을 뿐 문제 자체는 크게 어렵지 않았다.

 

물의 깊이에 따라 안전한 구역이 다르기 때문에, 최대 높이부터 하나씩 물이 잠기는 상황에 맞게 구현하였는데 이 과정에서 2차원 배열에서 최대 값을 간단하게 구하는 방법을 찾았다.

max_value = max(map(max,area))

바로 map 함수를 사용하여 각 행들의 최대 값들을 구한 뒤, 최대 값을 구하는 방식이었다.

 

그리고 물의 깊이가 달라질 때마다 방문 여부도 초기화 시켜주어야 하기 때문에 하나의 깊이가 끝날 때마다 visited 배열을 초기화 시켜주었다.

 

탐색 알고리즘을 사용하여 색다른 상황을 해결할 수 있었던 좋은 문제였다 :)