1. DFS Reference Code - 노드 유형, 백준 1260, 10971

 

 

 

Q. DFS 로 갈 수 있는 모든 경로의 수는?

 

#include <stdio.h>
#include <iostream>
using namespace std;

int map[30][30], ch[30], cnt = 0;
int n, m;

void DFS(int v){            // v -> 정점 번호
    if(v == n) {
        cnt++;
    }
    else {
        for(int i=1; i<=n; i++){
            if(map[v][i] == 1 && ch[i] == 0){
                ch[i] = 1;                          // 한 번 길 갈 때, 똑같은 곳을 또 방문하지 않기 위해
                DFS(i);
                ch[i] = 0;
            }
        }
    }
}

int main(void) {
    int a, b;
    
    scanf("%d%d", &n, &m);
    
    for(int i=0; i<m; i++){
        scanf("%d%d",&a,&b);
        map[a][b] = 1;
    }
    ch[1] = 1;
    DFS(1);
    printf("%d\n", cnt);
    
    return 0;
}
​

 

n = 정점의 개수, m = 간선의 개수

 

 

 

 

 

 

 

 

 

 

응용 문제) 백준 1260

 

www.acmicpc.net/problem/1260

1260번: DFS와 BFS

 

#include <stdio.h>
#include <iostream>
using namespace std;

int map[30][30], ch[30], cnt = 0;
int n, m, start;

void DFS(int v){            // v -> 정점 번호
    printf("%d ", v);
    
    if(cnt == n) {
        return;
    }
    else {
        for(int i=1; i<=n; i++){
            if(map[v][i] == 1 && ch[i] == 0){
                cnt++;
                ch[i] = 1;                          // 한 번 길 갈 때, 똑같은 곳을 또 방문하지 않기 위해
                DFS(i);
            }
        }
    }
}

int main(void) {
    int a, b;
    
    scanf("%d%d%d", &n, &m, &start);
    
    for(int i=0; i<m; i++){
        scanf("%d%d",&a,&b);
        map[a][b] = 1;
        map[b][a] = 1;
    }
    
    ch[start] = 1;
    cnt++;
    DFS(start);
    
    return 0;
}

 

 

 

- map[a][b] 만이 아닌, map[b][a]도 1로 설정

- 시작 정점을 1이 아닌, 값을 받아서 주고,

- 여러 경로를 탐색하기 위해 ch[i] = 0; 으로 풀어주는 과정을 지웠다.

 

 

 

 

 

 

 

 

 

 

 

 

응용문제) 백준 10971

www.acmicpc.net/problem/10971

10971번: 외판원 순회 2

 

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
using namespace std;
int W[11][11];
int visited[11];

int N;
int start;
long long int m = 98765432;

void dfs(int start, int n, int cost, int cnt){
    
    // 선택한 노드의 수가 총 개수이고, 시작 노드까지의 경로가 있으면
    if(cnt == (N-1) && W[n][start] != 0){
        cost += W[n][start];
        if(cost < m)
            m = cost;
        return;
    } else {
        for(int i=0; i<N; i++){
            
            if(n == i || W[n][i] == 0)
                continue;
            
            // 간 적이 없는 노드일 때
            if(visited[i] == 0){
                
                visited[i] = 1;
                dfs(start, i, cost + W[n][i], cnt+1);
                visited[i] = 0;
            }
        }
    }
}


int main(void) {

    scanf("%d", &N);
    
    for(int i=0; i<N; i++){
        for(int j=0; j<N; j++){
            scanf("%d", &W[i][j]);
        }
    }

    // 0에서 출발하는 것만 구해도 됨 -> 싸이클이 있기 때문에 다른 출발점으로 해도 동일함
    visited[0] = 1;
    dfs(0, 0, 0, 0);
    
    printf("%lld\n", m);
    
    return 0;
}

 

 

- 최소 비용 경로를 구하는 문제였음

- DFS 재귀 반복할 때마다 cost와 cnt 를 넣어주고, 나올 때는 다시 풀게 하여 모든 경우의 cost 와 cnt를 구할 수 있게 함