[알고리즘] 7-11 경로 탐색 - 인접행렬, 인접리스트, 깊이우선탐색(DFS) (인프런 자바(Java) 알고리즘 문제풀이 : 코딩테스트 대비 강의)

인프런의 자바(Java) 알고리즘 문제풀이 : 코딩테스트 대비 강의를 수강하며 풀이 코드를 정리하고 있습니다.

• 문제 설명 : 방향 그래프가 주어지면 1번 정점에서 N번 정점으로 가는 모든 경로의 가지 수를 출력하는 문제
• 입력 설명 : 첫째 줄에는 정점의 수 n과 간선의 수 m이 주어지고 다음 줄부터는 m 줄에 걸쳐 연결 정보가 주어진다.

인접행렬과 인접리스트 두 가지 방법으로 풀이한다. 정점의 개수가 많은 경우 인접행렬을 사용하면 그만큼의 2차원 배열을 만들어야 하기 때문에, 정점의 개수가 1000개, 10000개와 같이 많을 때는 인접리스트를 사용하는 것이 좋다.

그래프 이론에서 경로는 한번 방문한 노드를 다시 방문하지 않는다. 그래서 checked 배열을 통해 노드 방문 여부를 체크한다.

풀이1 - 인접행렬

package inflearn.recursive_tree_graph;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

//경로 탐색(인접행렬)
public class Main7_12 {

    static int[][] graph;
    static int[] checked; //방문 노드를 체크하는 용도
    static int n;
    static int answer;

    public static void dfs(int from) {

        if (from == 5)
            answer++;
        else {
            for (int i = 1; i <= n; i++) {
                if (graph[from][i] == 1 && checked[i] == 0) {
                    checked[i] = 1;
                    dfs(i);
                    checked[i] = 0; //i번 노드 방문이 끝났기 때문에 0으로
                }
            }
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        graph = new int[n + 1][n + 1];
        checked = new int[n + 1];
        answer = 0;

        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());

            int from = Integer.parseInt(st.nextToken());
            int to = Integer.parseInt(st.nextToken());

            graph[from][to] = 1;
        }

        checked[1] = 1;
        dfs(1);

        System.out.println(answer);

        br.close();
    }
}

풀이 2 - 인접리스트

package inflearn.recursive_tree_graph;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

//경로 탐색(인접리스트)
public class Main7_13 {

    static int n;
    static List<List<Integer>> graph;
    static int[] checked;
    static int answer = 0;

    public static void dfs(int v) {
        if (v == n)
            answer++;
        else {
            for (int nextV : graph.get(v)) {
                if (checked[nextV] == 0) {
                    checked[nextV] = 1;
                    dfs(nextV);
                    checked[nextV] = 0;
                }
            }
        }

    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine());

        n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        checked = new int[n+1];
        graph = new ArrayList<>();

        for (int i = 0; i <= n; i++) {
            graph.add(new ArrayList<>());
        }

        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());

            int from = Integer.parseInt(st.nextToken());
            int to = Integer.parseInt(st.nextToken());

            graph.get(from).add(to);
        }

        checked[1] = 1;
        dfs(1);

        System.out.println(answer);

        br.close();
    }
}