[백준] 2468번 : 안전 영역

문제

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

풀이

[백준] 2468 : 안전 영역 🥈(실버1)
🎯 34.428%
⏰ 걸린 시간 :30분

• 알고리즘 유형 : [BFS & DFS]

<✅ 문제 요약>

0. 지역마다 높이 정보가 주어진다.
1. 그 지역에 많은 비가 내렸을 때 물에 잡기지 않는 안전 영역이 최대 몇개 구역인지 구한다.
2. 내리는 비의 양에 따라 일정한 높이 이하의 모든 지점은 물에 잠긴다.

<✅ 출력>

첫째 줄에 장마철에 물에 잠기지 않는 안전한 영역의 최대 개수를 출력한다.

<✅ 풀이방법 & recursion DFS로 푼 이유?>

✔️ 재귀 함수를 돌면서 연결된 요소들을 하나로 보고 깊이 탐색이 유리
0. DFS 알고리즘 특성 깊이 탐색을 한다.
1. 해당 문제는 DFS는 안전 영역을 체크하는 것이다.
2. 깊게 탐색후 하나의 영역을 다 체크하고 나오는 것이 목표이기 때문에 DFS가 적합하다고 판단했다.

코드(code)

import sys
sys.setrecursionlimit(10000)
input = sys.stdin.readline

N = int(input())
graph = []
max_water = 0
dx = [0,0,-1,1]
dy = [-1,1,0,0]

for i in range(N):
    row = list(map(int,input().split()))
    max_water = max(max_water,max(row))
    graph.append(row)


# recursion DFS
def DFS(x,y,water):
    visited[x][y] = 1
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0 <= nx <= N-1 and 0 <= ny <= N-1 :
            if visited[nx][ny] == 0 and graph[nx][ny] > water:
                DFS(nx,ny,water)

safety_area=[]
for water in range(0,max_water+1):
    cnt = 0
    visited = [[0]*N for i in range(N)]
    for i in range(N):
        for j in range(N):
            if visited[i][j] == 0 and graph[i][j] > water :
                cnt += 1
                DFS(i,j,water)
    safety_area.append(cnt)

print(max(safety_area))

회고

recursion DFS는 이제 너무 익숙하다.

• BFS문제를 풀면서 더 익숙해져 보자

• [해당 코드]

  https://github.com/JamesJoe0830/ps_study/blob/main/BFS_DFS/2468(%EC%95%88%EC%A0%84%20%EC%98%81%EC%97%AD).py