Algorithm - Route Navigation ( Graph / DFS )

• 2023-12-23 에 풀이한 문제
• 문제 풀이 시간 : 1245 ~ 1303 ( 풀이 성공 )

• 나의 풀이 깃허브 : 풀이 클릭!

알고리즘 문제(Java) : 경로탐색 ( 그래프 / DFS )

1. 문제

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

2. 입력

• 첫째 줄에는 정점의 수 N(1<=N<=20)와 간선의 수 M이 주어집니다. 그 다음주터 M줄에 걸쳐 연결 정보가 주어집니다.

3. 출력

• 총 가지수를 출력합니다.

4. 문제 풀이

• 그래프의 인접 행열에 대하여 알아야 한다.
• 그래프와 인접행렬
  • Graph 는 Vertex 와 Edge 로 이루어져있다.
  • Vertex 는 Node 를 의미하고, Edge 는 Node 사이를 연결하는 선을 의미한다.
• 그래프에는
  • 무방향 그래프 ( 양방향 그래프 )
  • 방향 그래프 ( 단반향 그래프 )
  • 가중치 방향 그래프 이렇게 세 가지가 있다.
• 이걸 인접행렬 방식으로 만들어서 값을 구하면 아래와 같다.
  • 무방향은 양방향이므로,
    • 1 - 2 - 3 이면

    	1	2	3
    1	0	1	0
    2	1	0	1
    3	0	1	0

    
    

  • 방향 그래프는 단방향이므로
    • 1 -> 2 -> 3 이면

    	1	2	3
    1	0	1	0
    2	0	0	1
    3	0	0	0

    
    

  • 가중치 방향 그래프는
    • 1 –2–> 2 –5–> 3 이면

    	1	2	3
    1	0	2	0
    2	0	0	5
    3	0	0	0

  • 이렇게 된다.

public class Route_Navigation {

    static int n, m, answer = 0;
    static int[][] graph;
    static int[] ch;

    public static 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) {
        Scanner scan = new Scanner(System.in);
        n = scan.nextInt();
        m = scan.nextInt();
        graph = new int[n+1][n+1];
        ch = new int[n+1];
        for ( int i=1; i<=m; i++ ) {
            graph[scan.nextInt()][scan.nextInt()] = 1;
        }
        ch[1] = 1;
        DFS(1);
        System.out.println(answer);
    }
}