13. 경로탐색 (인접리스트, ArrayList)

1. 문제

ArrayList를 사용해서 정점 1에서 정점 5까지 가는 경우의 수를 출력하시오.

 

입력

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

 

출력

6

 

2 - 1. 나의 풀이

먼저 강의를 수강하고 여러가지 풀이(?)로 풀어보려함 (핵심은 같다.)

 

ArrayList<Integer> 를 담는 ArrayList를 생성하는 것이 핵심 (ArrayList<ArrayList<Integer>> graph)

 

 

2 - 2. 나의 코드

풀이 1.

public static void DFS(int num) {
       ArrayList<Integer> tmp = graph.get(num);
       for (int x : tmp) {
           if(x==5) count++;
           if(ch[x] == 0){
               ch[x] = 1;
               DFS(x);
               ch[x] = 0;
           }
       }

 

풀이 2.

public static void DFS(ArrayList<Integer> gp) {
    for (int x : gp) {
        if(x == 5) count++;
        if (ch[x] == 0) {
            ch[x] = 1;
            DFS(graph.get(x)); //인자값이 ArrayList<Integer>
            ch[x] = 0;
        }
    }
}

 

 

 

3 - 1. 강의 풀이

행렬에 저장해서 풀면 불필요한 접근이 많아진다 (10 * 10 행렬이면 100개의 인덱스에 접근해야한다.)

하지만 ArrayList는 정점간의 간선의 수만큼 생성되므로 속도가 훨 빠르고 효율적임

 

3 - 2. 강의 코드

package BFS_DFS;
import java.util.*;


public class ArrayList_13 {
    public static int[] ch;
    public static ArrayList<ArrayList<Integer>> graph;
    public static int n,m,count =0;

    public static void DFS(int num) {
     if(num == 5) count++;
        else{
             ArrayList<Integer> tmp = graph.get(num);
            for (int x : tmp) {
            if(ch[x] ==0){ //정점 x 를 방문하지 않았으면
                ch[x] = 1;
                DFS(x);
                ch[x]=0;
            	}
            }
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt(); //정점의 수
        m = sc.nextInt();
        graph = new ArrayList<ArrayList<Integer>>();

        for (int i = 0; i <= n; i++) { //graph를 0~n까지 AL를 만들어야함
            graph.add(new ArrayList<Integer>());
        }
        ch = new int[n + 1];
        //ArrayList에 연결해야함

        for (int i = 0; i < m; i++) {
            int v = sc.nextInt();
            int e = sc.nextInt();
            graph.get(v).add(e);
        }

        ch[1] = 1;
        DFS(graph.get(1));
        System.out.println(count);
    }

}

 

4. 얻어갈 점

복잡하게 보여도 천천히 순서를 생각하면서 풀자.