경로탐색 (인접 행렬 / 인접 리스트)

설명

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

1 2 3 4 5

1 2 5

1 3 4 2 5

1 3 4 5

1 4 2 5

1 4 5

총 6가지입니다.

 

 

입력

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

 

출력

총 가지수를 출력한다.

 

예시 입력 1 

5 9
1 2
1 3
1 4
2 1
2 3
2 5
3 4
4 2
4 5

 

예시 출력 1

6

 

 

문제 해결

 

1번 정점에서 시작하여 N번 정점으로 가는 모든 경로의 수를 찾는 문제이므로 DFS를 이용해 모든 경로를 탐색할 수 있다.

각 정점을 방문할 때마다 방문했다는 표시를 해두고, 탐색을 마친 후에는 그 표시를 지워 다른 경로에서 해당 정점을 다시 방문할 수 있게 해야 하는 것이 포인트이다.

 

< 인접 행렬 >

 

인접 행렬을 사용하는 방법에서는 연결 정보를 2차원 배열로 저장한다. 배열의 각 요소는 두 정점 사이의 연결 존재 여부를 나타낸다. (Matrix 배열을 통해 각 노드의 연결 정보를 저장하며, visited 배열은 노드 방문 여부를 체크)

static int N;
static boolean[][] Matrix;
static int countPaths;
static boolean[] visited;

public static void DFS(int node) {
    if (node == N) {
        countPaths++; // 도착 정점에 도달했다면 경로 수를 증가
        return;
    }

    visited[node] = true; // 현재 노드 방문 처리

    for (int nextNode = 1; nextNode <= N; nextNode++) {
        if (Matrix[node][nextNode] && !visited[nextNode]) {
            DFS(nextNode); // 다음 노드로 이동
        }
    }

    visited[node] = false; // 방문 처리 해제
}

• Matrix[i][j]는 노드 i에서 노드 j로의 연결을 의미 (연결이 있을 땐 true, 없을 땐 false)

 

< 인접리스트, ArrayList >

 

인접 리스트을 사용하는 방법에서는 각 정점의 인접 정점들을 리스트로 저장한다.

static int N;
static ArrayList<ArrayList<Integer>> List;
static int countPaths;
static boolean[] visited;

public static void DFS(int node) {
    if (node == N) {
        countPaths++; // 도착 정점에 도달하면 경로 수 증가
        return;
    }

    visited[node] = true; // 현재 노드 방문 처리

    for (int nextNode : List.get(node)) {
        if (!visited[nextNode]) {
            DFS(nextNode); // 다음 노드로 이동
        }
    }

    visited[node] = false; // 방문 처리 해제
}

• List[i]는 노드 i에서 출발하여 연결된 다른 노드들의 목록을 가진다. (노드 1이 노드 2와 노드 3에 연결되어 있다면, List[1]에는 2와 3이 포함되는 것)

 

인접 행렬은 빈번한 연결 확인이 필요하고 그래프가 밀집되어 있을 때 적합하며

인접 리스트는 그래프의 노드 수에 비해 간선 수가 많지 않은 희소 그래프에 적합하다.

 

( 인접 행렬은 공간 복잡도가 높아 연결이 적은 희소 그래프에서는 메모리 낭비가 심할 수 있으며

인접 리스트는 두 노드 간의 연결 여부를 확인하기 위해서는 리스트를 순회해야 하므로

최악의 경우 O(N)의 시간이 소요될 수 있다. )

 

 

최종 코드

 

< 인접 행렬 >

import java.util.Scanner;

public class P12_경로탐색_DFS {
    static int N;
    static boolean[][] Matrix;
    static int countPaths;
    static boolean[] visited;

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        N = in.nextInt();
        int M = in.nextInt();

        Matrix = new boolean[N + 1][N + 1]; //인접 행렬 초기화


        // 간선 입력
        for (int i = 0; i < M; i++) {
            int from = in.nextInt();
            int to = in.nextInt();
            Matrix[from][to] = true; // from -> to 경로
        }

        visited = new boolean[N + 1];

        countPaths = 0;
        DFS(1); //정점 1부터

        System.out.println(countPaths);
    }

    private static void DFS(int node) {
        if (node == N) {  //현재 노드가 N이면 경로를 찾은 것
            countPaths++;
            return;
        }

        //현재 노드 방문 처리 true
        visited[node] = true;


        // 모든 가능한 노드 탐색
        for (int nextNode = 1; nextNode <= N; nextNode++) {
            if (Matrix[node][nextNode] && !visited[nextNode]) { // 인접하고 방문하지 않은 노드
                DFS(nextNode);
            }
        }

        // 방문 처리 false
        visited[node] = false;
    }
}

 

< 인접 리스트 >

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

public class P13_경로탐색_인접리스트_ArrayList {
    static int N;
    static ArrayList<ArrayList<Integer>> List;
    static int countPaths;
    static boolean[] visited;

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        N = in.nextInt();
        int M = in.nextInt();

        List = new ArrayList<>();
        for (int i = 0; i <= N; i++) { //리스트 초기화
            List.add(new ArrayList<>());
        }

        // 간선 입력
        for (int i = 0; i < M; i++) {
            int from = in.nextInt();
            int to = in.nextInt();
            List.get(from).add(to);
        }

        visited = new boolean[N + 1];

        countPaths = 0;
        DFS(1); //정점 1부터

        System.out.println(countPaths);
    }

    private static void DFS(int node) {
        if (node == N) {  //현재 노드가 N이면 경로를 찾은 것
            countPaths++;
            return;
        }

        //현재 노드 방문 처리 true
        visited[node] = true;


        // 모든 인접 노드 탐색
        for (int nextNode : List.get(node)) {
            if (!visited[nextNode]) //방문하지 않았던 노드만 방문
                DFS(nextNode);
        }

        // 방문 처리 false
        visited[node] = false;
    }
}