[PS] 인프런 강의 - Graph 3. 경로 탐색(인접 리스트)

 

문제

방향그래프가 주어지면 1번 정점에서 N번 정점으로 가는 모든 경로의 가지 수를 출력하는 프로그램을 작성하세요.  (한번 방문한 노드는 다시 방문할 수 없습니다)

위 그래프에서 1번 정점에서 5번 정점으로 가는 가지 수는

 

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

 

총 6 가지입니다.

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

▣ 출력예제 1
6

 

풀이

사실 인접행렬 방법은 정점 개수가 많아지면 메모리 낭비도 되고 시간 복잡도도 길어진다.

N이 10000 이라고 하면, 이차원 배열의 크기가 10000 x 10000 만큼 필요하다.

그리고 1번 정점 부터 갈 수 있는 정점을 살필 때 1부터 10000까지 돌아야한다.

이럴 때는, 'Integer를 원소로 갖는 ArrayList' 를 원소로 갖는 인접 리스트(ArrayList)를 선언하고,

정점 i - i번 리스트로 매칭한다.  예를 들어 1번 정점이 갈 수 있는 정점은 1번 리스트에 순서대로 추가하는 것이다.

 

따라서 정점을 탐색할 때 리스트 사이즈까지만 돌면되어서 훨씬 효율적이다.

(※ 인덱스는 0 부터 시작함, 0번 리스트는 버림)
1번 정점 - 1번 리스트

 

2

3

4

2번 정점 - 2번 리스트

 

1

3

3번 정점 - 3번 리스트

4

 4번  정점 - 4번 리스트

2

5

5번 정점 - 5번 리스트

X

 

코드

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

public class Main {
	
	static int n, m, answer = 0;
	static ArrayList<ArrayList<Integer>> graph; //integer를 저장할 수 있는 ArrayList를 저장하는 ArrayList
	static int[] ch; //방문한 적이 있으면 값이 1
	
	public static 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) {
        Scanner in = new Scanner(System.in);
        
        n = in.nextInt();//정점의 수 1~20
        m = in.nextInt(); //간선의 수 
        graph = new ArrayList<ArrayList<Integer>>(); //인덱스 번호 = 정점 번호 1~n번
        ch = new int[n+1];
        
        for(int i=0; i<=n; i++) { //정점의 개수 +1 만큼 ArrayList 추가(0번 리스트는 버림)
        	graph.add(new ArrayList<Integer>()); //0번 인덱스 부터 시작된다
        }
        
        for(int i=0; i<m; i++) {
        	int a = in.nextInt();
        	int b = in.nextInt();
        		
        	graph.get(a).add(b);

        }
        
        ch[1] = 1; //1부터 시작
        DFS(1);
        System.out.println(answer);
    }
}