경로 탐색 ( 인접 리스트 )

문제. 방향그래프가 주어지면 1번 정점에서 N번 정점으로 가는 모든 경로의 가지 수를 출력한다.

해당 그래프에서 1번에서 5번 정점으로 가는 가지수를 구하시오.

 

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

 

입력 예시

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

 

답 : 6

 

 

나의 답변

public class Main {
    static int n, m, answer = 0;
    static int[] ck; // 각 노드의 방문 여부를 나타내는 배열
    static ArrayList<ArrayList<Integer>> graph; // 그래프를 표현하기 위한 인접리스트

    // 깊이 우선 탐색(DFS)을 수행하는 메서드
    public void DFS(int v) {
        if (v == n) // 현재 노드가 목표 도착지인 경우
            answer++; // 경로 카운트를 증가시킴
        else {
            for (int nv : graph.get(v)) { // 현재 노드에 연결된 모든 인접 노드에 대해 반복
                if (ck[nv] == 0) { // 인접 노드가 아직 방문되지 않은 경우
                    ck[nv] = 1; // 방문 표시
                    DFS(nv); // 해당 인접 노드를 방문하기 위해 재귀 호출
                    ck[nv] = 0; // 인접 노드 방문 완료 후 방문 표시 해제
                }
            }
        }
    }

    public static void main(String[] args) {
        Main T = new Main();
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt(); // 노드의 개수 입력
        m = sc.nextInt(); // 간선의 개수 입력
        ck = 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); // 그래프에 연결 정보 추가
        }

        ck[1] = 1; // 출발 노드를 방문 표시
        T.DFS(1); // DFS 호출하여 탐색 시작
        System.out.println(answer); // 모든 경로 탐색이 끝난 후 도착지에 도달한 횟수 출력
    }
}

 

for 루프의 조건을 i <= n으로 설정하는 이유 : 인덱스 i가 노드를 나타내고 실제 노드 번호는 1부터 n까지이다.

따라서 graph 리스트의 크기를 n+1로 만들어야한다. 이렇게 하면 인덱스 0은 사용하지 않고, 노드 번호와 인덱스가 일치하게 된다.