[알고리즘] BFS/DFS와 동적 계획법

 

 

 

1. BFS, DFS에 대해 

BFS의 기본 원리는 아주 간단하다. 그래프의 시작점에서 닿을 수 있는 모든 곳을 탐색하는 것이다. DFS는 이의 반대다. 그래프에서 가능한만큼 깊이 탐색하는 것이다. 

 

[알고리즘-4]그래프 – IREALISM

[알고리즘-4]그래프

 

두가지 개념을 정확히 이해하고 싶다면 위의 글을 먼저 읽고 오자.

 

BFS의 predecessor subgraph는 이렇게 나타낸다. 

 

$G_{\pi }=(V_{\pi },E_{\pi }),$

$\text{where}$

$V_{\pi }=\{v\in V\mid v.\pi \ne \text{NIL}\}\cup \{s\},$

$E_{\pi }=\{(v.\pi ,v)\mid v\in V_{\pi }\setminus \{s\}\}$

 

이에 대한 이해는 생각보다 어렵지 않다. 

 

BFS는 입력으로 그래프 G 와 시작점 s를 받는다.

BFS를 수행후 생기는 모든 subgraph는$G_{\pi }$로 나타낼 수 있다.

 

$V_{\pi }$는 vertex의 집합이다.

 

• $V_{\pi }$는 BFS 과정에서 발견된, predecessor가 존재하는 모든 vertex를 포함한다.
• 즉, BFS를 통해 발견된 vertex 중 부모 $v.\pi$가 존재하는 vertex v가 포함된다.
• 거기에 시작 vertex s는 predecessor가 없지만 항상 포함되니까 합집합으로 나타낸다.

 

$E_{\pi }$ 는 edge들의 집합이다. 

 

• $E_{\pi }$ 는 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 }),$

$\text{where}$

$E_{\pi }=\{(\pi [v],v)\mid v\in V\text{ and }$

$\pi [v]\ne \text{NIL}\}.$

 

이 또한 "DFS 그래프는 vertex와 edge로 구성되는데, edge에서 v는 DFS 트리나 숲에서 유효한 predecessor를 가지는 경우에만 포함된다."로 대충 풀이할 수 있다.

 

2. 동적 계획법 (DP) 에 대해 

 

동적 계획법의 핵심은 '노가다하지 말자' 이다. 

어떠한 문제는 두개 이상의 문제를 푸는 데 사용될 수 있기 때문에, 이 문제의 답을 여러번 계산하는 대신 한번만 계산하고, 그 결과를 재활용 해 효율을 향상시키자는 것이 핵심이다. 

 

동적 계획법의 알고리즘 구현은 다음의 두 단계로 이뤄진다.

 

1. 완전 탐색을 이용해 주어진 문제를 해결한다. 

2. 중복된 부분의 문제를 한 번만 계산해 메모이제이션을 적용한다. 

 

 

3. 백준: 1520 - 내리막 길 

1520번: 내리막 길

 

 

1. 이 문제는 시작점에서 더 낮은 숫자들로만 이동하여 마지막 좌표까지 도달할 수 있는 모든 경로의 개수를 출력하는 것이다. 단순 DFS는 $4^{(500\times 500)}$ 만큼의 탐색을 요구할 수 있으므로 시간 초과가 발생한다. 이를 해결하기 위해 DFS와 DP를 결합해 메모이제이션을 사용한다.
2. $DP[a][b]$ 는 (a, b)에서 (N-1, M-1)까지 도달할 수 있는 경로의 수를 의미한다. 탐색 도중 이미 계산된 좌표에 도달하면 $DP$ 값을 바로 활용하여 중복 탐색을 방지한다.
3. $DP$ 배열은 초기 값을 -1로 설정한다. $DP[a][b]=-1$ 은 아직 탐색하지 않은 좌표를 의미하며, $DP[a][b]=0$ 은 해당 좌표에서 마지막 지점까지 갈 수 있는 경로가 없음 을 나타낸다. 이를 통해 탐색이 필요한 좌표와 아닌 좌표를 구분한다.
4. 이 방식으로 탐색하면 중복 작업을 줄이면서도 조건을 만족하는 경로의 개수를 효율적으로 계산할 수 있다.

 

#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 참고