[자료구조]그래프와 인접 리스트

 

 

 

경로 탐색 (인접행렬)

 

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

입력 설명
첫 째 줄에는 정점의 수 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

출력 예제
6

 

📌 코드 구현

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

public class Prac {

	static int n, m, count = 0;
	
	static ArrayList<ArrayList<Integer>> graph;
	
	static boolean[] check;
	
	public static void main(String[] args){
		
		Scanner sc = new Scanner(System.in);
		
		n = sc.nextInt();  // 정점 수
		m = sc.nextInt();  // 간선 수
		
		graph = new ArrayList<>();
		
		for(int i=0; i<=n; i++)
			graph.add(new ArrayList<>());
		
		check = new boolean[n+1];
		
		for(int i=0; i<m; i++) {
			int from = sc.nextInt();
			int to = sc.nextInt();
			
			graph.get(from).add(to);
		}
		
		check[1] = true;
		DFS(1);
		System.out.println(count);
	}
	
	static void DFS(int v) {
		if(v == n) {
			count++;
			return;
		}
		
		for(int i : graph.get(v)) {
			if(!check[i]) {
				check[i] = true;
				DFS(i);
				check[i] = false;
			}
		}
	}
	
}

6