[알고리즘] 깊이 우선 탐색(DFS)

 

그래프 탐색

그래프 탐색은 하나의 노드에서 시작하여 모든 노드를 차례로 한 번씩 방문한다.

 

깊이 우선 탐색(Depth First Search : DFS)

DFS는 그래프 탐색 중 하나로 루트 노트 또는 정해진 노드로부터 시작하여 최대한 깊이 탐색한 후 더 이상 갈 곳이 없으면 다시 원점으로 돌아와 다른 루트를 탐색하는 방식이다.

모든 노드를 방문하고자 할 경우 이 방법을 선택하고, 스택 또는 재귀함수를 통해 구현한다.

 

너비 우선 탐색(BFS)보다는 간단하지만 검색 속도가 비교적 느리다.

---

 

• 예제 코드

public class DfsExam1 {
      static int T;  // 테스트 케이스
      static int N;  // 조합하고자 하는 숫자, 경우의 수
      static int visited[] = new int[7]; // 방문한 값 체크
      static int Answer[] = new int[7];

      static void dfs(int depth) {
          // 종료 조건
          if (depth == N + 1) { 
              for (int i = 1; i <= N; i++) {
                  System.out.print(Answer[i] + " ");
              }
              System.out.println();
          } else { // 탐색 조건
              for (int i = 1; i <= N; i++) { 
                  if (visited[i] == 0) {
                      visited[i] = 1;    
                      Answer[depth] = i; 
                      dfs(depth + 1);  // 재귀함수 호출
                      visited[i] = 0;  
                      Answer[depth] = 0;
                  }
              }
          }
      }

      public static void main(String[] args) {

          Scanner sc = new Scanner(System.in);
          T = sc.nextInt();
          for (int test_case = 1; test_case <= T; test_case++) {
              N = sc.nextInt();

              for (int i = 1; i <= N; i++) {
                  visited[i] = 0;
              }
              System.out.print("#" + test_case);        
              dfs(1);
          }

      }
    }

결과값

 

---

 

[외판원 순회 문제]

1번부터 N번까지 번호가 매겨져 있는 도시가 있고, 도시를 사이에 길이 있는 경우에만
이동할 수 있다. 여행을 좋아하는 종민이는 M번 도시에서 출발하여 출발지를
제외한 모든 도시를 정확히 한 번씩만 방문한 후 처음 출발지인 M번 도시로
돌아오려 한다. 이때 도시들 사이의 길을 지날갈 때 지불해야 하는 통행료가 있어,
종민이는 최소한의 비용으로 모든 도시를 여행하고 싶다. 종민이가 모든 도시를
여행할 때 필요한 최소비용을 출력하는 프로그램을 작성하시오.

[입력]
첫 번째 줄에 테스트케이스의 수 T(1<= T <= 10)가 주어진다.
각 테스트케이스 마다 첫 번째 줄에는 도시의 수 N과 출발지 M이 공백을 두고 주어진다.
(3<=N<=10, 1<=M<=N) 다음 N개의 줄에는 각 줄에 N개의 숫자들이 공백을
두고 주어지는데 i번째 줄의 j번째 숫자는 i번째 도시에서 j번째 도시로 가는 드는
통행료 MAT[i][j]를 의미한다. 만약 통행료가 0인 경우는 i도시에서 j도시로 가는 길이
없음을 의미하다. (0<=MAT[i][j]<=50)

[제한조건]
- 도시를 잇는 도로는 일방통해이다. 심지어 i번째 도시에서 j번째 도시로 가는
길은 있어도, j번째 도시에서 i번째 도시로 가는 길은 없을 수도 있다.
- 모든 도시를 정확히 한 번씩만 지나야 함에 유의하라.

[출력]
각 줄마다 "#T(T는 테스트케이스 번호)를 출력한 뒤, 종민이가 M번 도시부터
시작하여 모든 도시를 정확히 한 번씩 순회하고 오는데 드는 통행료 최소값을
출력하시오. 단 불가능할 경우 -1을 출력한다.

 

• 문제풀이

public class DfsExam2 {
      static int T;
      static int N, M;
      static int Answer;
      static int MAT[][] = new int[11][11];
      static int visited[] = new int[11];

      public static void dfs(int idx, int cost, int cnt) {
          //종료조건(모든 도시를 방문했을 때)
          //시작점으로 돌아갈 길이 있는 경우만
          if(cnt == N) {
              if(MAT[idx][M] != 0) {    
                  //기존 답보다 새로운 비용이 더 적은 경우
                  if(Answer == -1 || Answer > cost + MAT[idx][M]) {
                   Answer = cost + MAT[idx][M];    
                  }
              }
              System.out.println();
          } else { //탐색조건            
              //방문한 적이 없고, 길이 있는 도시만 검색
              for(int i = 1; i <= N; i++) {            
                  if(visited[i] == 0 && MAT[idx][i] != 0) {
                     //가지치기 (기존 정답보다 누적비용이 적은 경우 탐색 필요)
                      if(Answer == -1 || Answer > cost+ MAT[idx][i]) {
                      visited[i] = 1;                                  
                     dfs(i, cost+ MAT[idx][i], cnt+1);
                     visited[i] = 0;
                     }        
                  }
              }        
          }
      }        

      public static void main(String[] args) {

          Scanner sc = new Scanner(System.in);
          T = sc.nextInt();
          for (int test_case = 1; test_case <= T; test_case++) {
              N = sc.nextInt(); //도시 수
              M = sc.nextInt(); // 출발도시

              for(int i = 1; i <= N; i++) {
                  for(int j = 1; j <= N; j++) {
                      MAT[i][j] = 0;
                  }
              }
              for(int i = 1; i <= N; i++) {
                  visited[i] = 0;
              }

              for(int i = 1; i <= N; i++) {
                  for(int j = 1; j <= N; j++) {
                      MAT[i][j] = sc.nextInt();
                  }
              }

              visited[M] = 1;
              Answer = -1;
              //DFS 탐색(위치, 비용(누적된 비용값, 최소값), 현재까지 방문한 도시의 수)
              dfs(M, 0, 1);
              System.out.println("#" + test_case + " " + Answer);
          }
      }
   }

결과값

---