[JAVA] 알고리즘 : 경로탐색(DFS)

 

 

 

인접 행렬 사용

import java.util.Scanner;

public class Main{
    static int n, m, answer=0;
    static int[][] graph;
    static int[] ch;
    public void DFS(int v){
        if(v==n) answer++; // n번 노드면
        else{
            for(int i=1; i<=n; i++){
                if(graph[v][i] == 1 && ch[i]==0){ // 갈 수 있는 노드라면
                    ch[i]=1;
                    DFS(i); // v에서 i로 이동
                    ch[i]=0; // 돌아오면 체크 풀어줌
                }
            }
        }

    }
    public static void main(String[] args) {
        Main T = new Main();
        Scanner kb = new Scanner(System.in);
        n=kb.nextInt();
        m=kb.nextInt();
        graph = new int[n+1][n+1]; // 1번 인덱스부터 n번 인덱스까지 정점번호
        ch = new int[n+1];
        for(int i=0; i<m; i++){
            // a에서 b로 감
            int a = kb.nextInt();
            int b = kb.nextInt();
            graph[a][b]=1; // 방향 그래프
        }
        ch[1]=1; // 1번 노드 체크
        T.DFS(1); // 1번부터 출발
        System.out.println(answer);
    }
}

 

 

 

정점의 개수가 많아지면 ArrayList를 사용하는게 효율적이다. 

 

 

 

인접 리스트 사용

 

import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.Scanner;

public class Main{
    static int n, m, answer=0;
    static ArrayList<ArrayList<Integer>> graph; // Integer를 저장하는 ArrayList를 저장하는 ArrayList
    static int[] ch;
    public void DFS(int v){
        if(v==n) answer++;
        else{
            for(int nv : graph.get(v)) {// v번째 arrayList
                if(ch[nv]==0){ // nv라는 정점을 방문 안했다면
                    ch[nv]=1; // 방문으로 체크
                    DFS(nv);
                    ch[nv]=0; // 방문 체크 품
                }
            }
        }
    }
    public static void main(String[] args) {
        Main T = new Main();
        Scanner kb = new Scanner(System.in);
        n=kb.nextInt();
        m=kb.nextInt();
        graph = new ArrayList<ArrayList<Integer>>();
        for(int i=0; i<=n; i++){
            graph.add(new ArrayList<Integer>()); // 정수를 저장할 수 있는 ArrayList 객체 생성
        }
        ch=new int[n+1];
        for(int i=0; i<m; i++){
            int a = kb.nextInt();
            int b = kb.nextInt();
            graph.get(a).add(b); // a번째 ArrayList에 b추가
        }
        ch[1]=1;
        T.DFS(1);
        System.out.println(answer);
    }
}