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

1. 개요

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

2. 의사 코드(pseudocode)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

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]

• 풀이)

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49

  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); } } } }