섹션 7 Recursive, Tree, Graph - 11. 경로탐색 (인접행렬)

📌 문제 설명

방향 그래프가 주어졌을 때,
1번 정점에서 N번 정점으로 가는 모든 경로의 개수를 구하는 프로그램을 작성한다.

예를 들어 아래 그래프에서 1 → 5로 가는 경로는 총 6가지다.

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

---

📝 입력 & 출력

입력

• 첫 줄에 정점의 수 N(1 ≤ N ≤ 20), 간선의 수 M이 주어진다.
• 다음 M줄에 걸쳐 방향 간선 정보 A B가 주어진다. (A → B)

출력

• 1번 정점에서 N번 정점으로 갈 수 있는 모든 경로의 가지 수를 출력한다.

---

🔹 예제 입력 & 출력

예제 입력

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

 

예제 출력

6

---

💡 해결 방법

• 정점 간 연결 정보를 인접행렬로 저장
• DFS를 사용해 1번 정점에서 시작해서 N번 정점에 도달할 때마다 경로 수 증가
• 방문 배열을 사용해 이미 방문한 노드는 다시 방문하지 않도록 한다
• DFS가 종료되면 해당 노드는 방문 해제 (백트래킹)

---

💻 코드 구현 (Java)

전체 코드

package partRecursiveTreeGraph;

import java.util.*;

public class Problem11 {
	static int n, m, answer = 0;
	static int[][] graph;
	static int[] ch;

	public void DFS(int v) {
		if (v == n) answer++;
		else {
			for (int i = 1; i <= n; i++) {
				if (graph[v][i] == 1 && ch[i] == 0) {
					ch[i] = 1;
					DFS(i);
					ch[i] = 0;
				}
			}
		}
	}

	public static void main(String[] args) {
		Problem11 T = new Problem11();
		Scanner kb = new Scanner(System.in);
		n = kb.nextInt();
		m = kb.nextInt();
		graph = new int[n+1][n+1];
		ch = new int[n+1];
		for (int i = 0; i < m; i++) {
			int a = kb.nextInt();
			int b = kb.nextInt();
			graph[a][b] = 1;
		}
		ch[1] = 1;
		T.DFS(1);
		System.out.print(answer);
	}
}

---

📖 코드 설명

1️⃣ 인접행렬 초기화

graph = new int[n+1][n+1];

• 방향 그래프는 2차원 배열을 사용한 인접행렬로 표현
• graph[a][b] = 1이면 정점 a에서 b로 이동 가능

---

2️⃣ 방문 체크 배열

ch = new int[n+1];

• DFS에서 사이클 방지 및 중복 경로 방지를 위해 방문 여부 체크

---

3️⃣ DFS 함수

 

public void DFS(int v) {
	if (v == n) answer++;
	else {
		for (int i = 1; i <= n; i++) {
			if (graph[v][i] == 1 && ch[i] == 0) {
				ch[i] = 1;
				DFS(i);
				ch[i] = 0;
			}
		}
	}
}

• v == n: 목적지 N번 정점 도달 → answer++
• graph[v][i] == 1 && ch[i] == 0: 다음 이동 가능한 정점이면서 아직 방문하지 않았을 때만 이동
• DFS(i) 호출 후 → 다시 돌아와 방문 해제 (백트래킹)

---

4️⃣ DFS 시작

ch[1] = 1;
T.DFS(1);

• 시작 정점은 1번
• 방문 체크한 뒤 DFS 탐색 시작

---

⏳ 시간 복잡도 분석

• 그래프의 구조에 따라 탐색 경로 수는 지수적으로 증가할 수 있다.
• DFS는 모든 경로를 완전탐색하기 때문에
• 시간 복잡도는 O(총 경로 수 × 평균 경로 길이) 수준이다.
• 하지만 N ≤ 20이므로 모든 경로를 탐색해도 실행 시간상 문제 없다.

---

🧠 핵심 정리

• 방향 그래프는 인접행렬로 표현
• DFS를 통해 1번에서 N번까지 도달하는 모든 경로를 탐색
• 중복 경로 방지 위해 방문 배열 사용 + 백트래킹 필수
• 시간 복잡도는 N이 작을 때만 완전탐색 가능

---

출처: 인프런 자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비

https://www.inflearn.com/course/자바-알고리즘-문제풀이-코테대비/dashboard

자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비 강의 | 김태원 - 인프런