[DFS] 12. 경로탐색

<<풀이>>

 

이번에는 경로탐색을 DFS 방식으로 풀었다.

 

이번 1번에서 5번까지 가는 경로 갯수를 탐색하는 것인데

 

우선 1번이 갈 수 있는 값이 간선으로 연결되어 있는 자기 자신을 제외한 값이다.

 

그 값이 있다면 그 값으로 이동을 하고 똑같은 값으로는 갈 수 없기에 ch(체크) 배열에 그값과 같은 인덱스에 1을 추가해준다.

 

이번 문제를 풀면서

DFS 방식은 DFS(n + 1) 또는 DFS(2n) 과 이전 DFS(n)과 연관(연산 등)되어 움직였지만, 이번에는 연관이 있다기 보다 만족하는 값이 들어가서 재귀함수를 사용했다. 

 

이렇게 여러가지 DFS를 보니 조금 더 감을 잡을 수 있는 계기가 되었다!!

import java.util.Scanner;

class Main {
  

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

    public static void main(String[] args) {
        Main T = new Main();
        Scanner in = new Scanner(System.in);
        arr = new int[m + 1][m + 1];
        n = in.nextInt();
        m = in.nextInt();
        ch = new int[j + 1];

        for(int i = 0; i < m; i++) {
            int a = in.nextInt();
            int b = in.nextInt();
            arr[a][b] = 1;
        }
        ch[1] = 1;
        T.DFS(1);

        System.out.println(answer);
    }
}