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

 

https://hyejin.tistory.com/1262

자바 알고리즘 문제 풀이 입문. ch07. Recursive, Tree, Graph(DFS, BFS 기초) : Tree 말단 노드까지의 가장 짧

-> 이전 문제 풀이 

 

 

 

11. 경로 탐색 (인접행렬) 

설명

방향그래프가 주어지면 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
{
   static int n, m, cnt = 0;
   static int[][] graph;
   static int[] ch;
   
   public int DFS(int v)
   {
      if (v == n) {
         cnt++;
      }else {
         for (int i = 1; i <= n; i++)
         {
            if (graph[v][i] == 1 && ch[i] == 0) {
               ch[i] = 1;
               DFS(i);
               ch[i] = 0; // 빽한 시점에서는 0으로 바꿔줘야 함
            }
         }
      }
      
      return cnt;
   }
   
   public static void main(String[] args)
   {
      RouteNavigation routeNavigation = new RouteNavigation();
      Scanner scanner = new Scanner(System.in);
      n = scanner.nextInt();
      m = scanner.nextInt();
      graph = new int[n + 1][n + 1];
      ch = new int[n + 1];
      
      for (int i = 0; i < m; i++)
      {
         int a = scanner.nextInt();
         int b = scanner.nextInt();
         graph[a][b] = 1;
      }
      
      ch[1] = 1;
      int result = routeNavigation.DFS(1);
      System.out.println(result);
      
   }
}

👾 : 먼저 인접행렬을 2차원 배열 graph 로 푸는 방법이다. 

그리고 ch 배열을 하나 더 만들고 해당 노드를 방문했는지 체크하는 배열로 사용할 것이다. (방문했으면 1, 아니면 0) 

 

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

맨 처음 노드 1부터 시작할 것이기 때문에 ch[1] = 1로 체크하고, 그 다음 DFS 메서드를 호출한다. 

 

public int DFS(int v)
{
   if (v == n) {
      cnt++;
   }else {
      for (int i = 1; i <= n; i++)
      {
         if (graph[v][i] == 1 && ch[i] == 0) {
            ch[i] = 1;
            DFS(i);
            ch[i] = 0; // 빽한 시점에서는 0으로 바꿔줘야 함
         }
      }
   }
   
   return cnt;
}

DFS 메서드에서는 이제 val 이 n (마지막 노드)이면 cnt의 개수를 +1 해주면 되고, 아니면 

for문을 1부터 n 까지 돌면서 재귀 함수를 수행해주면 된다.

이때 graph[v][i] == 1 이어야 하고, 그 다음 ch[i]가 방문한 적이 없어야 (0) 

ch[i] = 1 로 변경해서 (방문한다고 체크), DFS(i) 를 다시 호출한다. 

 

->  DFS(1) -> ch[2]를 방문한다고 1 체크하고,  DFS(2) 를 호출한다. 

-> DFS(2) 에서 ch[1], ch[2]는 1이기 때문에 ch[3] 을 1 체크하고, DFS(3) 호출한다. 

-> DFS(3) 에서 ch[1], ch[2], ch[3] 은 1이므로 ch[4] 을 1 체크하고, DFS(4) 호출한다. 

-> DFS(4)  에서는 ch[1], ch[2], ch[3], ch[4] 는 1이므로 ch[5] 를 체크하고 DFS(5)를 호출한다. 

-> DFS(5) 는 v == n 에 해당하므로 cnt ++ ; 해주고 종료한다.  -> 1 2 3 4 5 

 

-> DFS(3)으로 돌아와서 graph[3][5] 1이 아니므로 DFS(3) 도 종료한다. 

-> DFS(2) 로 돌아와서 graph[2][4], graph[2][5] 를 볼 때 graph[2][5] = 1 이므로 DFS(5)를 호출한다. 

-> DFS(5) 는 v == n 에 해당하므로 cnt ++; 해주고 종료한다. -> 1  2 5 

(종료할 때는 이제 방문 해제를 해주기 위해 ch[i] = 0 을 해줘야 한다.) 

 

-> 그리고 다시 DFS(1) 로 돌아와서 2는 했으니 DFS(3) 을 호출한다. 

이걸 계속 반복해주면 됨..! 

 

 

 

1 2 3 4 5

1 2 5

1 3 4 2 5

1 3 4 5

1 4 2 5

1 4 5