경로탐색(DFS, 인접리스트)

이 문제는 방향 그래프에서 1번 정점에서 시작하여 N번 정점까지 가는 모든 경로의 수를 구하는 문제이다. 이 문제를 해결하기 위해 DFS(깊이 우선 탐색)과 인접 리스트를 사용한다. 이 방식은 그래프를 효율적으로 탐색하고, 경로의 수를 빠르게 구할 수 있다.

 

문제 해결 접근

1. 그래프의 표현

• 그래프는 정점과 간선으로 이루어진 자료 구조이다. 이 문제에서는 방향 그래프로, 정점에서 다른 정점으로 갈 수 있는 방향이 정해져 있다.
• 그래프는 인접 리스트를 사용하여 표현한다. 이는 ArrayList를 이용해 각 정점에서 연결된 다른 정점들을 리스트 형태로 저장하는 방식이다.

2. DFS(깊이 우선 탐색)

• DFS는 한 경로씩 끝까지 탐색하며, 마지막 정점(N번 정점)에 도달할 때마다 경로의 수를 카운트한다.
• 각 경로를 탐색한 후에는, 그 경로가 끝나면 다시 돌아와서 다른 경로를 탐색할 수 있도록 백트래킹을 적용한다.

3. 방문 체크 배열

• 방문 체크 배열(ch)을 사용하여, 이미 방문한 정점을 다시 방문하지 않도록 관리한다.
• 백트래킹을 위해, 탐색이 끝난 후 다시 해당 정점을 방문할 수 있도록 방문 체크를 해제해 준다.

package com.example.codingtest;

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

public class Main {
    static int n, m, answer = 0;  // 정점의 수(n), 간선의 수(m), 총 경로의 수(answer)
    static ArrayList<ArrayList<Integer>> graph;  // 그래프를 인접 리스트로 표현
    static int[] ch;  // 방문 체크 배열

    // DFS 함수: 깊이 우선 탐색으로 경로를 찾는다
    public void DFS(int v) {
        if (v == n) {  // 마지막 정점에 도착하면
            answer++;  // 경로 수를 하나 증가시킨다
        } else {
            for (int nv : graph.get(v)) {  // 현재 노드와 연결된 다른 노드 탐색
                if (ch[nv] == 0) {  // 아직 방문하지 않은 노드라면
                    ch[nv] = 1;  // 방문 처리
                    DFS(nv);  // 다음 노드로 재귀 호출
                    ch[nv] = 0;  // 백트래킹: 방문 해제
                }
            }
        }
    }

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

        String[] str = br.readLine().split(" ");
        n = Integer.parseInt(str[0]);  // 정점의 수
        m = Integer.parseInt(str[1]);  // 간선의 수
        graph = new ArrayList<>();

        // 그래프 초기화
        for (int i = 0; i <= n; i++) {
            graph.add(new ArrayList<>());  // 각 정점에 빈 리스트 할당
        }

        ch = new int[n + 1];  // 방문 체크 배열 초기화

        // 간선 정보 입력
        for (int i = 0; i < m; i++) {
            String[] str2 = br.readLine().split(" ");
            int a = Integer.parseInt(str2[0]);
            int b = Integer.parseInt(str2[1]);
            graph.get(a).add(b);  // a에서 b로 가는 간선 추가
        }

        ch[1] = 1;  // 시작 노드 방문 처리
        T.DFS(1);  // DFS 탐색 시작
        System.out.println(answer);  // 경로의 총 가지 수 출력
    }
}

 

1. 그래프의 인접 리스트 구현

그래프라는 자료 구조를 사용해, 각 정점이 다른 정점과 어떻게 연결되어 있는지 표현해야 한다. 이 문제에서 방향 그래프는 각 정점에서 나가는 간선이 어디로 연결되는지 중요하다. 인접 리스트를 사용하면 각 정점에서 연결된 정점들을 효율적으로 저장할 수 있다.

• 인접 리스트는 ArrayList<ArrayList<Integer>>로 구현된다. 여기서 각 정점은 연결된 정점들을 ArrayList로 저장한다.
• 입력된 간선 정보는 graph.get(a).add(b)를 통해 a에서 b로 가는 간선을 추가한다.

예를 들어, 입력 예시에서

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

이 그래프를 인접 리스트로 표현하면

graph = [    [],        // 0번 정점은 사용하지 않음
    [2, 3, 4], // 1번 정점은 2, 3, 4번과 연결
    [1, 3, 5], // 2번 정점은 1, 3, 5번과 연결
    [4],       // 3번 정점은 4번과 연결
    [2, 5],    // 4번 정점은 2, 5번과 연결
    []         // 5번 정점은 연결된 정점이 없음
]

이 구조에서 각 정점에 대해 연결된 정점들이 리스트로 저장되므로, 효율적인 탐색이 가능하다.

 

2. DFS(깊이 우선 탐색)

DFS는 그래프에서 한 경로를 끝까지 탐색한 뒤, 다시 돌아와 다른 경로를 탐색하는 방식이다. 이 문제에서는 1번 정점에서 출발하여 5번 정점까지 가는 모든 경로를 찾는 것이 목표다.

• 재귀 호출을 이용하여 DFS를 구현한다. 1번 정점에서 출발한 뒤, 연결된 다른 정점들을 차례대로 탐색하면서 5번 정점에 도착할 때마다 경로 수(answer)를 증가시킨다.
• 탐색이 끝나면 다시 이전 정점으로 돌아가서, 다른 경로를 탐색하기 위해 백트래킹을 적용한다.

예시: DFS 탐색 흐름

1. 1번 정점에서 시작한다.
2. 1번 정점에서 2번, 3번, 4번으로 갈 수 있다.
3. 2번 정점으로 가서, 5번 정점에 도착하면 경로를 하나 찾았다. 다시 돌아와서 다른 경로를 탐색한다.
4. 3번 정점에서 4번을 거쳐 5번에 도착하는 경로를 찾는다.
5. 이 과정을 반복하여 모든 경로를 탐색한 후, 경로의 수를 출력한다.

3. 방문 체크와 백트래킹

그래프 탐색 중 같은 경로를 중복으로 탐색하지 않도록 하기 위해 방문 체크 배열(ch)을 사용한다. 이를 통해 각 정점을 한 번만 방문하도록 하고, 탐색이 끝난 후에는 백트래킹을 통해 다시 방문할 수 있도록 체크를 해제한다.

• ch[nv] = 1: 해당 정점을 방문했음을 표시한다.
• ch[nv] = 0: 백트래킹 과정에서 다시 방문할 수 있도록 방문 체크를 해제한다.

백트래킹은 재귀를 통해 호출한 함수가 끝났을 때, 이전 상태로 돌아가 다른 경로를 탐색할 수 있도록 해주는 역할을 한다.

 

4. 최종 경로의 수 출력

DFS 탐색을 마친 후, 모든 경로를 찾고 나면, 변수 answer에 경로의 수가 저장된다. 이를 최종적으로 출력하면 문제의 정답이 된다.

 

예시 풀이

주어진 입력 예제

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

이 입력에서 총 6가지 경로가 발견된다.

• 1 → 2 → 5
• 1 → 3 → 4 → 5
• 1 → 3 → 4 → 2 → 5
• 1 → 4 → 5
• 1 → 4 → 2 → 5
• 1 → 2 → 3 → 4 → 5

이처럼 DFS와 인접 리스트를 통해 효율적으로 모든 경로를 탐색하고 경로의 수를 구할 수 있다.