그래프 순회

그래프 순회란 그래프 탐색이라고도 불리며 그래프의 각 정점을 방문하는 과정을 이야기 한다.

그래프 순회는 크게 깊이 우선 탐색(Depth First Search)와 너비 우선 탐색(Breadth First Search)의 2가지 알고리즘이 있다.

그래프 순회

DFS

- 일반적으로 BFS에 비해 더 널리 쓰인다.

- 코테에서도 그래프 탐색은 주로 DFS로 구현하게 된다.

- 주로 스택이나 재귀로 구현하며 백트래킹을 통해 뛰어난 효용을 보인다

 

앞서 말했듯 DFS는 스택으로 구현하며 재귀를 이용 하면 좀 더 간단하게 구현 할 수 있다. 코테에서도 재귀 구현이 더 선호된다.

 

재귀 구조로 구현

해당 사진은 위키피디아에 제시된 수도코드이다. 

수도코드 DFS

 

이 수도코드에서 정점 v(vertex)의 모든 인접 유향(Directed) 간선들을 반복하라고 표기되어 있다. 이 수도코드의 알고리즘을 동일하게 파이썬 코드로 구현해보면 다음과 같다.

재귀를 활용한 DFS

graph는 맨위 사진과 일치한다. recursive_dfs의 입력으로는 점1개(v)와 여태까지 발견한 점의 집합을 나타내는 discovered 리스트로 이루어져 있다. 처음은 당연히 발견한 점이 없으니 빈 리스트를 넣어준다. 2번째 줄에는 입력으로 들어온 v를 발견했으니 discoverd에 넣어준다. 그다음 발견한 점에 연결된 다른 점을 차례대로 탐구한다. 그 이후에는 2가 들어가고 그이후에는 다시 recursive_dfs 함수로 들어가고 이는 다시 2가 연결된 5로 들어간다. 즉, 깊이를 너비보다 먼저 탐색한다는 것을 알 수 있다. 

 

stack을 활용한 DFS

이는 stack을 이용하여 DFS를 구현 하였다. while은 stack이 없을때 까지 계속 진행한다. 즉 stack은 모든 점을 다 탐색하므로 다 탐색하기 전까지는 while이 끝나지 않는다. 6번째 줄은 점이 여태까지 발견하지 않은 점이면 해당 점에 연결된 점 여기서 헷갈리는 것은 얼핏 보기엔 BFS로 보인다는 것이다. 하지만 stack은 앞으로 횡단할 점들을 나타내는 것이고 실제로 DFS로 탐색할 점은 discovered에 저장된다는 것이다. 그래서 맨처음 1이 들어오면

stack = [1],

stack에 1이 있으므로 들어와서 v는 1

그리고 1은 발견되지 않았으므로 discovered = [1]

여기서 graph[1]에 있는 모든 점을 stack에 넣어준다. 그럼 stack은 [2,3,4]가 들어오고 여기서 다시 stack의 pop이 되므로 4가 먼저 탐색되어 

v 는 4가 되고 discovered에는 [1,4]

그다음 4가 연결된것이 없으므로 그다음이 5로 가는 형식이다. 

즉 stack으로 인해 DFS로 구현되는 것을 알 수있다. 

 

BFS

- 주로 큐로 구현한다(최적화를 위해 데크를 사용하는것도 좋다.)

- 그래프의 최단 경로를 구하는 문제등에서 사용된다. 

- 즉, 다익스트라 알고리즘에 유용하게 사용된다.

- BFS는 재귀로 풀이할 수 없다. 

 

bfs 구현

DFS와 다르게 BFS는 찾은 순서대로 discovered에 더해주는 것을 볼 수있다. 

 

 

백트랭킹

- 해결책에 대한 후보를 구축해 나아가다 가능성이 없다고 판단되는 즉시 후보를 포기(backtrack)해 정답을 찾아가는 범용적인 알고리즘으로 제약 충족 문제에 특히 유용하다.

 

탐색해야 하는 가지가 많은 트리

 

트리를 탐색하여 가능성이 없는 후보를 포기하는 백트래킹의 예

 

 

DFS를 이야기하다보면 항상 백트래킹이라는 단어가 함께 나온다. 백트래킹은 DFS보다 좀 더 강의의  의미를 가진다. 백트래킹은 탐색을 하다가 더 갈수 없으면 왔던 길을 되돌아가 다른 길을 찾는다는 데서 유래했다.

백트래킹은 DFS와 같은 방식으로 탐색하는 모든 방법을 뜻하며, DFS는 백트래킹의 골격을 이루는 알고리즘이다.

백트래킹은 주로 재귀로 구현하며, 알고리즘 마다 DFS 변형이 조금씩 일어나지만 기본적으로 모두 DFS의 범주에속한다. 백트래킹은

가보고 되돌아오고를 반복한다. 운이 좋으면 시행착오를 덜 거치고 목적지에 도착 할 수 있지만 최악의 경우 모든 경우를 다 거친 다음에 도착할수 있기 때문에 브루트포스와 유사하다. 하지만 한번 방문 후 가능성이 없는 경우 즉시 후보를 포기한다는 점에서 매번 같은 경로를 방문하는 브르트 포스보다는 훨씬 더 우수한 방식이라고 할 수 있다.

이를 트리의 가지치기(pruning)라고 하며, 이처럼 불필요한 부분을 일찍 포기한다면 탐색을 최적화 할 수 있기 때문에, 가지치기는 트리의 탐색 최적화 문제와도 관련이 깊다. 

 

 

제약 충족 문제

백트래킹은 제약 충족 문제(Constraint Satisfaction Problems(CSP))를 풀이하는 데 필수적인 알고리즘이다. 

제약 충족 문제란 수만은 제약 조건을 충족하는 상태를 찾아내는 수학문제를 말한다.

이는 합리적인 시간 내에 문제를 풀기 위해 휴리스틱과 조합탐색 같은 개념을 함께 결합해 문제를 풀이한다.

제약 충족 문제는 스도쿠처럼 1에서 9까지 숫자를 한번만 넣는(제약 조건 충족) 정답(상태)을 찾아내는 모든 문제 유형을 말한다.