[인프런] 07_12 경로 탐색(인접행렬) 07_13 경로탐색(인접리스트)

📖  문제

---

• 첫째 줄에는 정점의 수 N(1<=N<=20)와 간선의 수 M가 주어진다. 그 다음부터 M줄에 걸쳐 연결정보가 주어진다
  • 방향그래프가 주어지면 1번 정점에서 N번 정점으로 가는 모든 경로의 가지 수를 출력하는 프 로그램을 작성하세요.
  • 아래 그래프에서 1번 정점에서 5번 정점으로 가는 가지 수는 총 6 가지입니다.

문제 방향 그래프

출력 예시

 

⚠️  주의사항

---

• 한 번 갔던 곳을 되돌아오지 않게끔 주의해야 합니다.
• 만약 정점까지 도착했다면 지금까지 도착했던 곳의 체크를 해제해야 합니다.
• 행렬 / 리트스 두 가지의 방법으로 풀기

 

✍️  이해

---

• 행렬

/**
 * 1. N과 M, M개 만큼의 연결 정보 입력
 * 1-1. 체킁요 배열 ch, 탐색용 graph 생성
 * 2. DFS(1) 호출
 * 3. v == N -> answer 증가
 * 4. else
 *  4-1. for(i = 1 ~ N)
 *   4-1-1. graph[v][i] == 1 && ch[i] == 0
 *   4-1-2. 현재 체크 배열 1 입력
 *   4-1-3. DFS(i) 호출
 *   4-1-4. 현재 체크 배열 0 초기화
 */

• 리스트

/**
 * 1. Java07_12과 기본적인 개념은 똑같지만 N이 20이 아닌 10,000개 100,000개 등 늘어나게 될 경우 인접리스트 방식이 더 효율적임
 * 2. 5개라고 쳤을 때 1,2,3,4,5라는 리스트가 먼저 생성 돼야함
 * 3. 위의 리스트에 추가로 값이 들어가는것이므로 graph.get(앞 입력 값).add(뒤 입력 값
 * 4. for문이 아닌 for each 사용
 */

 

✏️  풀이

---

• 행렬

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++;
        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) {
        Main T = new Main();
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        M = sc.nextInt();

        graph = new int[N + 1][N + 1];
        ch = new int[N + 1];

        for (int i = 0; i < M; i++) {
            int a = sc.nextInt();
            int b = sc.nextInt();
            graph[a][b] = 1;
        }
        ch[1] = 1;
        T.DFS(1);
        System.out.println(answer);
    }
}

---

• 리스트

import java.util.ArrayList;
import java.util.Scanner;

public class Main {

    static int N, M, answer = 0;
    static int[] ch;
    static ArrayList<ArrayList<Integer>> graph;

    public void DFS(int V) {

        if (V == N) answer++;
        else {
            for (int i : graph.get(V)) { // ArrayList에는 for-each가 제일 나음
                if (ch[i] == 0) {
                    ch[i] = 1;
                    DFS(i);
                    ch[i] = 0;
                }
            }
        }
    }
    public static void main(String[] args) {

        Main T = new Main();

        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        M = sc.nextInt();

        ch = new int[N + 1];
        graph = new ArrayList<ArrayList<Integer>>();

        for (int i = 0; i <= N; i++) { // 객체 생성
            graph.add(new ArrayList<Integer>());
        }

        for (int i = 0; i < M; i++) {
            int A = sc.nextInt();
            int B = sc.nextInt();

            graph.get(A).add(B); // A번 리스트에 접근 후 A리스트에 B값 추가
        }
        ch[1] = 1;
        T.DFS(1);
        System.out.println(answer);
    }
}

---