문제해결 전략 - 28. 그래프 깊이 우선 탐색

BFS vs DFS visualization (credit:  https://github.com/kdn251/interviews ).

그래프 탐색 알고리즘

• 그래프의 모든 정점을 특정한 순서에 따라 방문하는 알고리즘
• 트리보다 구조가 훨씬 복잡하기 떄문에 탐색 과정에서 얻어지는 정보가 중요하다.
• 탐색과정에서 알 수 있는 정보
  • 어떤 간선이 사용되었는지
  • 어떤 순서로 정점들이 방문되었는지

깊이 우선 탐색(Depth-first search)

• 그래프의 모든 정점을 발견하는 가장 단순하고 고전적인 방법
  • 정점과 인접한 간선들을 하나씩 검사하다가, 아직 방문하지 않은 정점으로 향하는 간선이 있다면 해당 간선을 무조건 따라감
  • 더이상 갈곳이 없는 정점에 도달하면 마지막에 따라왔던 간선을 따라 뒤로 이동
• 탐색의 각 과정에서 가능한 한 그래프 안으로 '깊이' 들어가려고 시도한다.
• 지금까지 거쳐온 정점들을 모두 알고 있어야 하는데 재귀호출을 이용하면 간단히 구현할 수 있다.
  • 재귀호출 한 함수가 종료되면 호출한 위치로 다시 돌아가기 때문

• 그래프 전체의 구조를 파악하기 위해 사용됨

[DFS 예제코드]

Depth First Search or DFS for a Graph - GeeksforGeeks

---

깊이 우선 탐색의 시간 복잡도

• 그래프 표현 방식에 따라 달라진다.
• LinkedList
  • 인접 간선을 검사하는 for 문에 의해 지배된다.
  • Time complexity: O(V + E), where V is the number of vertices and E is the number of edges in the graph.
  • Space Complexity: O(V).
    Since, an extra visited array is needed of size V.

---

예제

• 연결된 부분집합의 개수 세기
  • 주어진 그래프가 몇 개의 컴포넌트로 구성되어 있는지 파악하는 문제
    컴포넌트 : 무향 그래프가 간선으로 서로 연결되지 않은 몇 개의 조각으로 쪼개져 있는 경우, 각 연결된 정점들의 부분집합
  • DSFUtil을 호출하는 횟수를 세면 된다.
• 위상 정렬
  • 의존성이 있는 작업들이 주어질 때, 이들을 어떤 순서로 수행해야 하는지 계산하는 문제
  • 각 작업을 정점으로 표현하고, 작업 간 의존간계를 간선으로 표현한 방향 그래프를 의존성 그래프라고 한다.
  • 그래프에 사이클이 없다.(DAG)
  • 모든 의존성이 만족되려면 모든 간선이 왼쪽에서 오른쪽으로 가야 한다.
  • 이렇게 DAG의 정점을 배열하는 문제를 위상정렬이라고 한다.
  • dfs를 수행하여 dfs가 종료할 때 마다 현재의 정점의 번호르 기록한다.
    dfs가 종료한 뒤 순서를 뒤집으면 위상 정렬 결과를 얻을 수 있다.

---

문제

• 고대어 사전
  • 각 알파벳을 정점으로 표현하고 한 알파벳이 다른 알파벳 앞에 와야 할 때 두 정점을 방향 간선으로 연결한다.
  • 이 그래프에 사이클이 있는지 확인하고 없다면 위상 정렬결과를 반환한다.
  • 사이클이 존재하지 않는다면 옳은 위상 정렬 결과를 찾아낼 테니 반환된 순서에서 오른쪽에서 왼쪽으로 가는 간선이 존재하는지만 확인하면 된다.
• 오일러 서킷 : 그래프의 모든 간선을 정확히 한 번씩 지나서 시작점으로 돌아오는 경로 찾기
  • 한붓 그리기 문제
  • 오일러 서킷이 존재하지 않는 경우 : 그래프의 간선들이 두 개 이상의 컴포넌트에 나뉘어 있는 경우 존재 할 수 없다.
  • 각 정점에 인접한 간선의 수가 오일러 서킷의 존재 가능성과 밀접한 연관이 있다.
  • 그래프의 모든 정점들이 짝수점(degree 가 짝수) 이여야만 오일러 서킷이 존재할 수 있다.
• 오일러 트레일 : 그래프의 모든 간선을 정확히 한 번만 지나지만, 시작점과 끝 점이 다른 경로
  • 오일러 서킷을 찾는 문제로 변환
  • a시작 b 끝나는 오일러 트레일 찾기. a와 b 사이에 간선 (b,a)를 추가한 뒤 오일러 서킷을 찾는다. 그리고 (b, a) 간선을 지워서서킷을 끊는다.

---

이론적 배경과 응용

• 깊이 우선 탐색과 간선의 분류
  • 일부간선을 따라가고 나머지는 무시한다. 이 간선들을 무시하지 않고 이들에 대한 정보를 수집하면 그래프의 구조에 대한 많은 것을 알 수 있다.
  • 탐색이 따라가는 간선들만 모으면 트리 형태를 띈다.
  • 이런 트리를 DFS 스패닝 트리라고 부른다.
• 사이클 존재 여부 확인하기
  • 사이클의 존재 여부는 역방향 간선의 존재 여부와 동치이다.
• 이 정점이 몇번째로 발견되었는지도 동시에 기록한다. 이 정보를 이용해 순방향과 역방향 그리고 교차 간선을 구분해 낼 수 있다.
  
  • 발견 순서 정보를 이용하면 해당 간선이 순방향 간선인지 알아 낼 수 있다.
• 절단점 찾기 알고리즘
  • 그래프의 절단점 찾는 문제
  • 해당 정점을 그래프에서 삭제 한 뒤, 컴포넌트의 개수가 이전보다 늘어났는지 확인한다.
  • 각 정점의 발견 순서를 비교하는 형태로 구현을 간단하게 할 수 있다.
  • 깊이 우선 탐색 함수가 해당 정점을 루트로 하는 서브트리에서 역바양 간선을 통해 닿는 정점들을 최소 발견 순서를 반환하면 된다.

---