[Problem Solving] 백준 2468번 안전 영역 파이썬

백준 2468번 안전 영역 문제에 대한 해설과 코드입니다. 문제는 다음의 링크를 참고해주시면 됩니다. 문제 해설

 

문제의 설명에도 있지만 해당 문제는 비가 내리는 양이 정해져 있지 않아서 모든 영역이 잠기기 전까지의 경우를 모두 탐색해야 합니다. 따라서 해결 과정은 다음과 같습니다.

 

1. 가장 높은 지역의 높이를 구한다.
2. 비의 양에 따라 낮은 지역을 물에 잠기게 한다.
3. 물에 잠기지 않은 영역의 개수를 계산하여 저장한다.
4. 비의 양을 늘려 2를 반복한다.

물에 잠기는 부분과 잠기지 않는 부분을 구분하기 위해서 물에 잠기는 부분은 -1로 값을 변환시켰습니다. 낮은 지역부터 물에 잠기게 하기 때문에 한번 잠긴 지역은 결과가 나올 때까지 물에 잠겨있습니다는 것을 가정하고 진행합니다. 다음은 코드입니다.

 

# 백준 No.2468 안전 영역
from collections import deque

def setMaps(instability):
  for i in range(n):
    for j in range(n):
      visited[i][j] = False
      if maps[i][j] <= instability:
        maps[i][j] = -1

def dfs(x, y):
  queue = deque()
  queue.append((x,y))
  visited[x][y] = True

  dx = [-1, 0, 1, 0]
  dy = [0, -1, 0, 1]

  while queue:
    x, y = queue.popleft()

    for i in range(4):
      nx = x + dx[i]
      ny = y + dy[i]

      if nx >= 0 and nx < n and ny >= 0 and ny < n:
        if not visited[nx][ny] and maps[nx][ny] != -1:
          visited[nx][ny] = True
          queue.append((nx, ny))

n = int(input())

maps = []
max_maps = 0
visited = [[False] * n for _ in range(n)]
answer = []

for i in range(n):
  maps.append(list(map(int, input().split(" "))))
  if max_maps < max(maps[i]):
    max_maps = max(maps[i])

for i in range(max_maps):
  setMaps(i)
  count = 0
  for i in range(n):
    for j in range(n):
      if maps[i][j] != -1 and not visited[i][j]:
        count += 1
        dfs(i, j)
  answer.append(count)

print(max(answer))

 

setMaps 함수는 비의 양에 따른 물에 잠기는 지역을 -1로 바꿔주고, dfs에 사용되는 visited 배열을 초기화해줍니다. dfs는 물에 잠기지 않은 영역의 개수를 구하기 위해 사용되는 함수입니다. 비의 양에 따른 안전한 영역의 개수를 answer에 저장해주고 마지막에 가장 큰 값을 출력하는 것으로 해결하였습니다.