[C++] 경로 탐색 (DFS)

// 64번 경로 탐색

#include <vector>
#include <string>
#include <iostream>

using namespace std;
// 정점의 수 N
int N = 5;
// 간선의 수 M
int M = 9;
vector<vector<int>> line = {
    {1, 2},
    {1, 3},
    {1, 4},
    {2, 1},
    {2, 3},
    {2, 5},
    {3, 4},
    {4, 2},
    {4, 5}
};
vector<vector<int>> graph(N+1,vector<int>(N+1,0));

// 1번에서 5번 까지만 가면 됨ㅇㅇ
int answer = 0;
vector<int> tmp;
void DFS(int L,vector<int> visited){

    if (L == N){
        answer += 1;
        return;
    }
    for(int i = 1; i < N+1; i++){
        if (graph[L][i] == 1 && visited[i] == 0){
            visited[i] = 1;
            DFS(i,visited);
            visited[i] = 0;
        }
    }

}

int main(){
    
    for(auto l : line){
        int a = l.front();
        int b = l.back();
        graph[a][b] = 1;
    }
    vector<int> visited(N+1,0);
    visited[0] = 1;
    visited[1] = 1;
    for (int i = 1; i < N+1; i++){
        if (graph[1][i] == 1 && visited[i] == 0){
            visited[i] = 1;
            DFS(i,visited);
            visited[i] = 0;
        }
        
    }
    cout << answer;


    return 0;
}

 

양방향인지 단방향인지 확인 주의할것

 

그래프는 대부분 인접행렬로 풀어서 풀면 쉽게 풀린다.