DFS - 백준 2468번 :안전영역

오늘도 역시 굉장히 어려운 문제였어용....

문제 : 백준 2468번: 안전영역

해당 문제는 그래프 탐색 문제였고, DFS / BFS 의 개념이 필요했습니다.

문제를 정확히 풀기 위해 먼저 그래프 탐색의 개념을 정리해보았습니다.

📌 그래프(Graph)란?
정점(Node)과 정점을 연결하는 간선(Edge)으로 구성된 자료구조입니다.

그래프 탐색은 하나의 정점에서 시작해 모든 정점을 탐색하는 것입니다.

DFS (Depth-First Search)

---

• 깊이 우선 탐색
• 하나의 경로를 최대 깊이까지 계속 들어가며 탐색하고,
  더 이상 갈 곳이 없으면 이전 경로로 백트래킹(되돌아감)
• 스택 또는 재귀 함수로 구현 가능

BFS ( Breadth-Frist Search)

---

• 너비 우선 탐색
• 현재 위치에서 갈 수 있는 모든 노드를 먼저 탐색하고,
  다음 깊이로 내려가는 방식
• 큐(Queue) 자료구조를 사용해서 구현

2가지 탐색 방법은 문제에 따라 적합도가 나뉘는데

상황	유리한 탐색 방식	이유
전체 노드를 전부 탐색	둘 다 사용 가능	시간 제한이 크지 않다면 자유롭게 선택 가능
최단거리 구하기	BFS	BFS는 먼저 도착한 경로가 가장 짧은 거리
경로 조건, 제약 조건 추적	DFS	DFS는 한 경로를 끝까지 탐색하기 때문에 경로의 특징 유지 가능

최단거리

• 왜? BFS는 너비 우선 방식으로, 현재 노드에서 가까운 노드부터 탐색하기 때문에
  도착 지점에 가장 먼저 도달하면 그 경로가 곧 최단 경로가 됩니다.
• DFS는 한쪽으로 깊이 파고들기 때문에, 먼 길부터 탐색해서
  최단거리를 나중에 찾을 수도 있습니다.
  
  
  

경로 ,제약 조건 추적

• 왜? DFS는 한 경로를 끝까지 따라가므로,
  그 경로가 어떤 조건을 만족하는지 중간에 판단하거나 기록하기에 적합합니다.
• 예: “횡단보도를 2번 이상 통과하지 말 것” 같은 조건
• 반면 BFS는 여러 경로를 동시에 확장해나가기 때문에
  개별 경로의 상태를 추적하는 데는 불리할 수 있습니다.

이번 문제는 각 비의 높이마다 안전 영역을 DFS로 탐색하여
최대 안전 구역의 개수를 구하는 시뮬레이션 문제였습니다.



DFS 로직을 반복적으로 재초기화하며 높이별로 탐색해야 했기 때문에,
"탐색 시 초기화 및 조건 체크가 매우 중요했던 문제" 였습니다.

N = 4

grid = """1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1"""


grid = list(map(lambda x: list(map(int, x.split(" "))), grid.split("\n")))

max_rain = max(max(grid)) # 지역의 최대 높이


# 상하좌우 탐색을 위함

xx = [-1,1,0,0]
yy = [0,0,-1,1]

res = 0 #최대 안전구역


def dfs(x,y,rain):
    checked[x][y] = True
    for k in range(4):
        nx , ny = x + xx[k] , y+ yy[k]
        if 0 <= nx < N and 0 <= ny < N:
            if grid[nx][ny] > rain and checked[nx][ny] is False:

                dfs(nx,ny,rain)
# 0 부터 최대 높이 이하까지 반복
for rain in range(max_rain+1):
    count = 0
    checked = [[False] * N for _ in range(N)]
    for i in range(N):
        for j in range(N):
            if grid[i][j] > rain and checked[i][j] is False:
                dfs(x=i,y=j,rain=rain)
                count += 1
    res = max(res,count)


print(res)