DFS (깊이 우선 탐색)

깊이 우선 탐색 (Depth-First Search)

1. 개요

• 그래프의 모든 정점을 발견하는 가장 단순하고 고전적인 방법
• 현재 정점과 인접한 간선들을 하나씩 검사하다가, 아직 방문하지 않은 정점으로 향하는 간선이 있다면 그 간선을 무조건 따라가는 것
• 중요한 특성은 더 따라갈 간선이 없을 경우 이전으로 돌아간다는 점
• 그렇기 때문에 재귀호출로 구현하는 경우가 많으며, 어떤 노드를 방문했는지 여부를 검사해야 한다.
• 
  1. 1을 방문 -> 2를 방문 -> 3을 방문 -> 4를 방문
  2. 더이상 갈 곳이 없으므로 3으로 back, 3에서 2로 back, 2에서 1로 back
  3. 1에서 인접한 노드인 5로 방문 -> 6을 방문 .....

2. 의사 코드(pseudocode)

void dfs(Node root) {
  if(root == null) {
    return;
  }
  // index 방문 후 방문 표시
  visit(root);
  // root 노드와 인접노드 방문
  for(Node n : root.rootList) {
    if(!n.visited) {
      // 방문하지 않았을 경우 재귀 탐색
      dfs(n);
    }
  }
}

3. 시간 복잡도

• 어떤 그래프 표현 방식을 사용하느냐에 따라 다르다.
  1. 인접 리스트로 표현하는 경우
     • dfs 는 한 정점마다 한 번씩 호출되고(V번),
     • dfs 한 번은 모든 인접 간선을 검사하는 for에 의해 결정된다. (E번)
     • 따라서 O(V+E)
  2. 인접 행렬을 사용하는 경우
     • dfs 의 호출 횟수는 그대로 (V번)
     • dfs 내부에서 다른 모든 정점을 순회하며 두 정점 사이에 간선이 있는가를 확인해야 하기 떄문에 O(V) 만큼의 시간이 걸림
     • 따라서 O(V^2)

4. 예제) 여행 경로 짜기

• 주어진 항공권을 모두 이용하여 여행경로를 짜려고 합니다. 항상 ICN 공항에서 출발합니다.

  항공권 정보가 담긴 2차원 배열 tickets가 매개변수로 주어질 때, 방문하는 공항 경로를 배열에 담아 return 하도록 solution 함수를 작성해주세요.

• 입출력 예

  tickets	return
  [[ICN, JFK], [HND, IAD], [JFK, HND]]	[ICN, JFK, HND, IAD]
  [[ICN, SFO], [ICN, ATL], [SFO, ATL], [ATL, ICN], [ATL,SFO]]	[ICN, ATL, ICN, SFO, ATL, SFO]

• 풀이)

  public class 여행경로 {
  
      static boolean visit[];
      static List<String> list = new ArrayList<>();
      static String route = "";
  
      public String[] solution(String[][] tickets) {
          visit = new boolean[tickets.length];
  
          for(int i = 0 ; i < tickets.length; i++) {
  
              String start = tickets[i][0];
              String desti = tickets[i][1];
  
              if(start.equals("ICN")) {
                  visit[i] = true;
                  route = desti + ",";
                  dfs(tickets, desti, 1);
                  visit[i] = false;
              }
          }
  
          Collections.sort(list);
          String[] answer = list.get(0).split(",");
          return answer;
      }
  
      public static void dfs(String[][] tickets, String end, int count) {
  
          route += end + ",";
  
          if(count==tickets.length) {
              list.add(route);
              return;
          }
  
          for(int i = 0 ; i < tickets.length ; i++) {
              String start = tickets[i][0];
              String desti = tickets[i][1];
  
              if(end.equals(start) && !visit[i]) {
                  visit[i] = true;
                  dfs(tickets, desti, count+1);
                  visit[i] = false;
                  route = route.substring(0, route.length()-4);
              }
          }
      }
  }