자바 알고리즘 문제 풀이 입문. ch07. Recursive, Tree, Graph(DFS, BFS 기초) : 경로 탐색 (인접리스트) DFS

 

https://hyejin.tistory.com/1263

자바 알고리즘 문제 풀이 입문. ch07. Recursive, Tree, Graph(DFS, BFS 기초) : 경로 탐색 (인접행렬) DFS

-> 이전 문제 풀이 

 

 

 

 

12. 경로 탐색 (인접 리스트) 

설명

방향그래프가 주어지면 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

 

 

문제 풀이 1

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

   public int 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;
            }
         }
      }

      return answer;
   }

   public static void main(String[] args)
   {
      RouteNavigation_list routeNavigationList = new RouteNavigation_list();
      Scanner scanner = new Scanner(System.in);
      n = scanner.nextInt();
      m = scanner.nextInt();
      graph = new ArrayList<>();
      for (int i = 0; i <= n; i++) { // get(5) 까지 하기 위해서 n까지 반복
         graph.add(new ArrayList<>()); // 정수를 저장하기 위한 Arraylist 객체 저장
      }
      ch = new int[n+1];

      for (int i = 0; i < m; i++) {
         int a = scanner.nextInt();
         int b = scanner.nextInt();
         graph.get(a).add(b);
      }

      ch[1] = 1;
      int result = routeNavigationList.DFS(1);
      System.out.println(result);
   }
}

👾 : 이전 문제 풀이에서 경로 탐색을 인접 행렬로 하는 방법을 배웠는데 사실 인접 행렬은 2차원 배열을 활용하는 것이기 때문에 노드의 개수가 늘어나면 이를 감당하기 힘들다. N이 만약 10000 이러면 10000 * 10000 배열을 만들어야 하기 때문에 계산 시간이 N이 클수록 점점 늘어난다. 

 

따라서 인접 행렬 보다는 인접 리스트를 활용해서 문제를 푸는 것이 더 좋다. 

인접 리스트를 활용할 때는 ArrayList 로 subGraph 리스트를  만들어서 subGraph.get(1) 에는 노드 1이 갈 수있는 노드 2, 3, 4 를 저장하고, subGraph.get(2)에는 노드 2가 향하고 있는 노드를 저장하고... 해서 

subGraph.get(1), subGraph.get(2),  subGraph.get(3),  subGraph.get(4),  subGraph.get(5) 를 저장하는 Arraylist를 만든다. 

-> ArrayList<Arraylist<Integer>> graph를 만들라는 뜻 ! ( ArrayList<subGraph> graph)

 

for (int i = 0; i <= n; i++) { // get(5) 까지 하기 위해서 n까지 반복
   graph.add(new ArrayList<>()); // 정수를 저장하기 위한 Arraylist 객체 저장
}
ch = new int[n+1];

for (int i = 0; i < m; i++) {
   int a = scanner.nextInt();
   int b = scanner.nextInt();
   graph.get(a).add(b);
}

ch[1] = 1;
int result = routeNavigationList.DFS(1);
System.out.println(result);

-> 메인 메서드에서 graph 를 초기화해줘야 하는데 노드 1 ~ 노드 5까지의 arraylist를 저장하기 위해서 for문을 통해 0부터 n까지 구해준다. (그래야 0은 제외하고 추가할 수 있음) 

그리고 for문을 통해서 graph.get(a) 를 통해 노드 a가 향할 수 있는 노드 b를 add 해준다. 

그리고 먼저 1부터 시작하기 때문에 ch[1]은 방문했다는 뜻으로 1로 변경해주고 DFS 메서드를 호출한다. 

 

public int 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;
         }
      }
   }

   return answer;
}

그리고 DFS는 인접 행렬에 비해 코드가 좀 더 간결해진 것을 확인할 수 있다. 

DFS는 기본 틀로 if-else로 가면 되는데 if에는 먼저 v가 n까지 갔다는 것은 말단 노드라는 뜻이기 때문에 DFS 메서드를 호출하지 않고 answer +1 해준다. 

 

만약 n 이 v가 아니라면 graph.get(v)를 통해 v 노드가 갈 수 있는 노드 nv 꺼내고, 이 노드 nv가 방문한 노드인지 확인해보고(ch[nv] ==1) , 방문하지 않은 노드라면 (ch[nv] == 0) ch[nv] 을 1로 바꾸고, DFS(nv)를 호출해서 nv 기준으로 또 이 과정을 반복해주면 된다.