1. BFS, DFS에 대해
BFS의 기본 원리는 아주 간단하다. 그래프의 시작점에서 닿을 수 있는 모든 곳을 탐색하는 것이다. DFS는 이의 반대다. 그래프에서 가능한만큼 깊이 탐색하는 것이다.
[알고리즘-4]그래프
『Disclaimer: 본 글은 대학원의 데이터과학 알고리즘 수업 및 데이터과학 입문서적에 관한 공부 내용을 정리하는 시리즈입니다. 본 내용은 필자가 전부 직접 요약하여 적은 개인 노트이며, 개인
irealist.org
두가지 개념을 정확히 이해하고 싶다면 위의 글을 먼저 읽고 오자.
BFS의 predecessor subgraph는 이렇게 나타낸다.
\(G_\pi = (V_\pi, E_\pi),\)
\(\quad \text{where} \)
\(\quad V_\pi = \{v \in V \mid v.\pi \neq \text{NIL} \} \cup \{s\}, \)
\(\quad E_\pi = \{(v.\pi, v) \mid v \in V_\pi \setminus \{s\}\}\)
이에 대한 이해는 생각보다 어렵지 않다.
BFS는 입력으로 그래프 G 와 시작점 s를 받는다.
BFS를 수행후 생기는 모든 subgraph는\( G_\pi \)로 나타낼 수 있다.
\( V_\pi \)는 vertex의 집합이다.
- 는 BFS 과정에서 발견된, predecessor가 존재하는 모든 vertex를 포함한다.
- 즉, BFS를 통해 발견된 vertex 중 부모 \( v.\pi \)가 존재하는 vertex v가 포함된다.
- 거기에 시작 vertex s는 predecessor가 없지만 항상 포함되니까 합집합으로 나타낸다.
는 edge들의 집합이다.
- 는 BFS 과정에서 각 vertex v와 그 부모 \( v.\pi \) 사이의 edge로 구성된다.
- s는 부모가 없으므로 포함되지 않는다.
- 각 간선 \( (v.\pi, v) \)는 BFS 트리에서 부모-자식 관계를 나타낸다.
BFS의 predecessor subgraph는 하나의 소스(시작점)만 있다면 하나의 트리를 형성한다. 그와 달리, DFS의 predecessor subgraph는 여러개의 트리를 생성한다.
DFS의 predecessor subgraph는 다음과 같이 나타낼 수 있다.
\(G_\pi = (V, E_\pi),\)
\(\quad \text{where}\)
\(\quad E_\pi = \{ (\pi[v], v) \mid v \in V \text{ and }\)
\(\quad \pi[v] \neq \text{NIL} \}.\)
이 또한 "DFS 그래프는 vertex와 edge로 구성되는데, edge에서 v는 DFS 트리나 숲에서 유효한 predecessor를 가지는 경우에만 포함된다."로 대충 풀이할 수 있다.
2. 동적 계획법 (DP) 에 대해
동적 계획법의 핵심은 '노가다하지 말자' 이다.
어떠한 문제는 두개 이상의 문제를 푸는 데 사용될 수 있기 때문에, 이 문제의 답을 여러번 계산하는 대신 한번만 계산하고, 그 결과를 재활용 해 효율을 향상시키자는 것이 핵심이다.
동적 계획법의 알고리즘 구현은 다음의 두 단계로 이뤄진다.
1. 완전 탐색을 이용해 주어진 문제를 해결한다.
2. 중복된 부분의 문제를 한 번만 계산해 메모이제이션을 적용한다.
3. 백준: 1520 - 내리막 길
- 이 문제는 시작점에서 더 낮은 숫자들로만 이동하여 마지막 좌표까지 도달할 수 있는 모든 경로의 개수를 출력하는 것이다. 단순 DFS는 \( 4^{(500 \times 500)} \) 만큼의 탐색을 요구할 수 있으므로 시간 초과가 발생한다. 이를 해결하기 위해 DFS와 DP를 결합해 메모이제이션을 사용한다.
- \( DP[a][b] \) 는 (a, b)에서 (N-1, M-1)까지 도달할 수 있는 경로의 수를 의미한다. 탐색 도중 이미 계산된 좌표에 도달하면 \( DP \) 값을 바로 활용하여 중복 탐색을 방지한다.
- \( DP \) 배열은 초기 값을 -1로 설정한다. \( DP[a][b] = -1 \) 은 아직 탐색하지 않은 좌표를 의미하며, \( DP[a][b] = 0 \) 은 해당 좌표에서 마지막 지점까지 갈 수 있는 경로가 없음 을 나타낸다. 이를 통해 탐색이 필요한 좌표와 아닌 좌표를 구분한다.
- 이 방식으로 탐색하면 중복 작업을 줄이면서도 조건을 만족하는 경로의 개수를 효율적으로 계산할 수 있다.
#include <iostream>
#include <vector>
#include <cstring>
const int MAX = 500;
using namespace std;
int dx[4] = { 0, 0, -1, 1 };
int dy[4] = { 1, -1, 0, 0 };
int M, N;
int map[MAX][MAX];
int cache[MAX][MAX];
int DFS(int y, int x){
if (y == M - 1 && x == N - 1)
return 1;
int &ans = cache[y][x];
if (ans != -1) return ans;
ans = 0;
for (int i = 0; i < 4; i++){
int ny = y + dy[i];
int nx = x + dx[i];
if (ny >= 0 && nx >= 0 && ny < M && nx < N){
if (map[ny][nx] < map[y][x])
ans += DFS(ny, nx);
}
}
return ans;
}
int main()
{
ios_base::sync_with_stdio(false);
cin >> M >> N;
memset(cache, -1, sizeof(cache));
for (int i = 0; i < M; ++i){
for (int j = 0; j < N; ++j){
cin >> map[i][j];
}
}
cout << DFS(0, 0) << "\n";
return 0;
}
4. 비고 & 참고문헌
이 글을 쓰며 LaTeX 포맷팅하는 것이 제일 어려웠다.
종만북 & introduction to algorithms 참고