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

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

2468번: 안전 영역

 

🎉🎉 문제

 

재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 안전한 영역이 최대로 몇 개가 만들어 지는 지를 조사하려고 한다. 이때, 문제를 간단하게 하기 위하여, 장마철에 내리는 비의 양에 따라 일정한 높이 이하의 모든 지점은 물에 잠긴다고 가정한다.

 

 

어떤 지역의 높이 정보가 주어졌을 때, 장마철에 물에 잠기지 않는 안전한 영역의 최대 개수를 계산하는 프로그램을 작성하시오. 

 

🎉🎉 풀이

☑️ SWSA 치즈문제랑 비슷한 문제인 것 같다

☑️ 비가 내리는 양에 따라 안전영역의 개수를 구하고 이전 비의 높이일 때 안전영역의 개수와 비교해서 계속 갱신해주는 게 핵심 로직이다

☑️ 건물과 건물이 이어져있는지 판단할 때 bfs 이용

☑️ 건물 높이가 1부터인 거고 비는 0부터 시작한다는 점 주의 (아무 건물도 잠기지 않는 경우가 있다는 게 비가 내리지 않는 경우를 말하는 것 같다)

 

 

 

🎉🎉 코드

import sys
sys.setrecursionlimit(10**6)

#침수되지 않은 지역과 이어진 지역 탐색
def dfs(i, j, n, rain):
  visited[i][j] = True

  di = [-1, 0, 1, 0]
  dj = [0, 1, 0, -1]

  for k in range(4):
    ni = i+di[k]
    nj = j+dj[k]

    if 0 <= ni < n and 0 <= nj < n:
      if not visited[ni][nj] and ground[ni][nj] > rain:
        dfs(ni, nj, n, rain)
        

  
#도시의 크기
n = int(input())

#건물의 높이 입력받기
ground = [list(map(int, input().split())) for _ in range(n)]

#최대 건물의 높이
maxheigh = 0

#도시에 존재하는 건물 중에서 최대 건물의 높이를 구하는 반복문
for i in range(n):
  maxheigh = max(maxheigh, max(ground[i]))

#안전지역의 개수
safegroundcnt = 0

#비가 안올 때 ~ 최대 건물 높이만큼 내릴 때
for rain in range(0, maxheigh+1):

  #탐색 방문체크
  visited = [[False]*n for _ in range(n)]
  
  #비의 양에 따라 달라질 안전지역의 개수
  temp = 0
  
  for i in range(n):
    for j in range(n):
      
      #아직 방문하지 않은 건물이고 건물의 높이가 비가 오는 것보다 높다면
      if not visited[i][j] and ground[i][j] > rain:
      
        #이어진 건물 탐색
        dfs(i, j, n, rain)
        #안전지역 추가
        temp +=1

  #가장 많은 안전지역을 가질 때를 구해야 하므로 전체 탐색이 끝나면 최종 안전지역의 개수를 갱신해준다
  safegroundcnt = max(safegroundcnt, temp)

#정답출력
print(safegroundcnt)