경로 탐색(인접 행렬)

문제. 방향그래프가 주어지면 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[][] graph; // 인접 행렬
    static int[] ck; // 방문 여부 체크 배열

    // DFS 함수: 주어진 그래프에서 모든 경로를 탐색하여 가지 수를 카운트하는 메서드
    public int DFS(int x) {
    	// 목표 정점에 도달한 경우
        if (x == n) answer++; // 경로의 가지 수 증가
        else {
            for (int i = 1; i <= n; i++) {
                if (graph[x][i] == 1 && ck[i] == 0) { // 연결되어 있고 방문하지 않은 정점인 경우
                    ck[i] = 1; // 해당 정점 방문 체크
                    DFS(i); // 다음 정점으로 DFS 호출
                    ck[i] = 0; // 백트래킹: 해당 정점 방문 해제
                }
            }
        }
        return 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 int[n + 1][n + 1]; // 인접 행렬 초기화
        for (int i = 0; i < m; i++) {
            int a = sc.nextInt(); // 간선의 시작 정점
            int b = sc.nextInt(); // 간선의 도착 정점
            graph[a][b] = 1; // 그래프에 간선 추가
        }
        ck[1] = 1; // 시작 정점 체크
        T.DFS(1); // DFS 호출
        System.out.println(answer); // 결과 출력
    }
}

 

1. 입력으로 주어진 정점의 개수 n과 간선의 개수 m을 입력받는다.
2. 그래프의 인접 행렬을 구성합니다. 각 간선 정보에 따라 인접 행렬의 해당 위치를 1로 설정한다.
3. 출발점인 1번 정점을 방문 체크하고 DFS를 호출한다.
4. DFS 함수에서는 현재 정점에서 연결된 모든 정점을 탐색하며 재귀적으로 호출합니다. 만약 목표 정점에 도달하면 answer 값을 증가시킨다.
5. 모든 경로를 탐색한 후에는 최종적으로 answer 값을 출력한다.

 

 

 

 

경로탐색 시 한번 방문한 곳은 다시 방문하지 않는다. 

 

 

참고 자료 출처:

https://www.inflearn.com/course/lecture?courseSlug=%EC%9E%90%EB%B0%94-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%AC%B8%EC%A0%9C%ED%92%80%EC%9D%B4-%EC%BD%94%ED%85%8C%EB%8C%80%EB%B9%84&unitId=72776&category=questionDetail&tab=curriculum