🥇 경로탐색(DFS) 인접행렬

🏆 문제

방향그래프가 주어지면 1번 정점에서 N번 정점으로 가는 모든 경로의 가지 수를 출력하는 프로그램을 작성하세요. 아래 그래프에서 1번 정점에서 5번 정점으로 가는 가지 수는

1 2 3 4 5
1 2 5
1 3 4 2 5
1 3 4 5
1 4 2 5
1 4 5

• 입력 설명
  첫 번째 줄에는 정점의 수 N(1<= N <= 20) 의 간선의 수 M가 주어진다. 그 다음부터 M줄에 거쳐 연결 정보가 주어진다.

• 출력 설명
  총 가지수를 출력한다.

🏆 풀이

main 메소드

public static void main(String[] args) {
        Main5 T = new Main5();
        Scanner kb = new Scanner(System.in);
        n = kb.nextInt();
        m = kb.nextInt();
        // 이 그래프르 왜 만들었을까?..?
        graph = new int[n+1][n+1];
        // 체크배열을 하기위해 만듬..
        ch = new int[n+1];
        for(int i=0;i<m;i++){
            int a = kb.nextInt();
            int b = kb.nextInt();
            graph[a][b] = 1;
        }
        ch[1] = 1;
        T.DFS(1);
        System.out.println(answer);
    }

• Main5클래스의 객체를 생성한다.
• Scanner를 이용해 n,m의 값(최종 노드, 간선의 수)를 입렵한다.
• ch[] 배열을 이용해 체크를 한다.
• Main 클래스의 객체 T에서 DFS메소드를 실행시킨다. 매개변수의 값은 1이다.
• T.DFS(1)을 실행하고 나온 answer의 값을 출력한다.

DFS 메소드

public void DFS(int v){
        if(v == n){
            answer++;
        }
        else{
            for(int i=1; i<=n; i++){
                if(graph[v][i] == 1 && ch[i] == 0){
                   ch[i] = 1;
                   DFS(i);
                   ch[i] = 0;
                }
            }
        }
    }

• n,m,answer, graph, ch를 전역변수로 한 이유는 DFS메소드에서도 사용 하기 위함이다.
• 매개변수로 넘어온 v와 메인메소드에서 입력한 n의 값이 같다면 answer++;를 해준다.
• 그 밖의 경우 간선의 갯수만큼 반복문을 이용해서 graph[v][i] ==1 && ch[i] ==0) 인 경우에 ch[i] = 1 을 해준다.
• DFS(i)를 실행해 위의 메소드 DFS를 다시 실행시킨다.

소스코드

package dfs_bfs;
import java.util.Scanner;

public class Main5 {
    static int n,m,answer = 0;
    static int[][] graph;
    static int[] ch;
    public void DFS(int v){
        if(v == n){
            answer++;
        }
        else{
            for(int i=1; i<=n; i++){
                if(graph[v][i] == 1 && ch[i] == 0){
                   ch[i] = 1;
                   DFS(i);
                   ch[i] = 0;
                }
            }
        }
    }

    public static void main(String[] args) {
        Main5 T = new Main5();
        Scanner kb = new Scanner(System.in);
        n = kb.nextInt();
        m = kb.nextInt();
        // 이 그래프르 왜 만들었을까?..?
        graph = new int[n+1][n+1];
        // 체크배열을 하기위해 만듬..
        ch = new int[n+1];
        for(int i=0;i<m;i++){
            int a = kb.nextInt();
            int b = kb.nextInt();
            graph[a][b] = 1;
        }
        ch[1] = 1;
        T.DFS(1);
        System.out.println(answer);

    }
}