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

문제

https://www.acmicpc.net/problem/2468

 

풀이

높이가 h이하인 지점을 모두 잠기게 만드는 비가 내린다고 했을 때, 물에 잠기지 않는 안전한 영역의 개수를 구하면 되는 문제이다.

비가 오지 않는 경우도 있을 수 있으므로 h = 0, 1, ..., (지역의 최대 높이 - 1) 에 대해 안전 영역의 개수를 모두 구하고, 그 중 최댓값을 구하면 답이 된다.

import sys
sys.setrecursionlimit(10**6)

N = int(input())
maps = []
max_h = 0  # 지역의 최대 높이 저장
for _ in range(N) :
  temp = list(map(int, input().split()))
  maps.append(temp)
  max_h = max(max_h, max(temp))


def dfs(x, y) :

  if (0 <= x < N) and (0 <= y < N) and n_maps[x][y] == 1 :
    n_maps[x][y] = 0
    dfs(x-1, y)
    dfs(x, y-1)
    dfs(x+1, y)
    dfs(x, y+1)
    return True

  return False


h = 0
answer = 0

while (h < max_h) :
  # n_maps : 지점의 높이가 h보다 높으면 1, 아니면 0으로 저장
  n_maps = [[0 for _ in range(N)] for _ in range(N)]  # n_maps의 값이 0인 곳은 물에 잠기는 곳
  for i in range(N) :
    for j in range(N) :
      if maps[i][j] > h :
        n_maps[i][j] = 1
      else :
        n_maps[i][j] = 0

  count = 0
  for i in range(N) :
    for j in range(N) :
      if dfs(i, j) == True :
        count += 1
  
  answer = max(answer, count)
  h += 1

print(answer)