컴언

파이썬에서 Trie (트라이) 구현하기

자료구조

들어가며: "자동 완성" 기능에 대한 이야기


구글에서 어떤 단어를 검색창에 치면 그 단어로 시작하는 다른 키워드를 보여주는데요, 이런 걸 자동 완성(Autocomplete) 라고 합니다. 자동 완성을 구현 하려면 키워드들을 리스트에 담아서, 유저 인풋이 들어올 때 마다 인풋으로 시작하는 키워드를 리스트에서 빼오면 될 겁니다. 하지만, 만약 550만 개의 글을 갖고 있는 영어 위키백과의 제목들을 가지고 자동 완성을 구현하라고 한다면  (실제 일본 모 회사의 올해 인턴 모집 스크리닝 과제였음 ㅋㅋ) 리스트 따위로는 안 되고, 훨씬 더 효율적인 자료구조가 필요합니다. 오늘 배울 Trie 가 이럴 때 필요한 자료구조입니다.



Trie: 트라이? 트리? 기본적인 개념

우선 이름이 좀 특이한데요, Trie는 컴퓨터에서 검색을 뜻하는 retrieval 에서 온 단어라고 합니다. Prefix tree 라고도 하는데 직관적이고 부르기도 쉬워서 이렇게 부르는 사람도 꽤 있습니다. 아무튼 Retrieval 에서 왔으니 트리라고 불러야 하지 않냐!! 라고 하실 수도 있지만... 트리(Tree)와 혼동을 피하기 위해서 대부분은 그냥 트라이라고 부릅니다. 이런 논란에 휘말리기 싫어서 이 글에서는 Trie 라는 영어 명칭을 쓰기로 하겠습니다 큭큭

사실 Trie 는 트리(Tree) 자료 구조의 일종입니다. 미리 말씀드리자면 Trie 에서 어떤 문자열을 검색할 때의 시간 복잡도는 O(m) 밖에 안 됩니다. (m: 문자열의 최대 길이) 그래서 다른 자료 구조에 비해 문자열을 검색하는 데 특화된 자료 구조임을  알 수 있습니다. 


위 그림은 names = ['Joe', 'John', 'Johnny', 'Jane', 'Jack'] 을 Trie 에 삽입한 결과인데요.


각 Node 는 

(1) 글자를 갖는 key = 한 글자 (ex. J, A, C, K)

(2) 단어의 마지막 글자인지를 알려주는 flag (Terminal)

로 이루어져 있습니다. 


예를 들어 John 의 경우 J > O > H > N 으로 차례대로 Trie 에 삽입이 되었고 마지막 글자 N 의 노드에는 Terminal 이라는 flag 를 박아줍니다. 이 flag 때문에 John 이 한 단어임을 알 수 있습니다. 

Johnny 의 경우 John 까지는 이미 노드가 있으니 ( J > O > H > N )원래 있는 노드를 활용하고, John 뒤에 ny를 넣은 다음 y를 마지막 글자로 flag해주면 되는 겁니다.


파이썬에서 Trie 를 구현해볼까요?

첫번째. Node 구현



1. key 필드는 단어의 글자 하나를 담는 데 이용합니다. 영어라면 알파벳만 들어갈 수 있겠죠.

2. data 필드는 사실상 마지막 글자를 나타내주는 flag 입니다. 원래 boolean 형 으로 간단하게 true/false 로 구분할 수도 있지만

저는 마지막 글자인 경우에  단어 전체를 data 필드에 저장하고, 아닌 경우에는 그냥 널로 두려고 합니다. 그 이유는 밑에 구현할 starts_with 메소드 때문인데요, 곧 설명 드리겠습니다.

(즉, Jack 의 경우 J > A > C > K 에서 마지막 글자인 K 노드의 data 필드에만 "Jack" 이 들어가고, 그 외 노드의 data 필드는 널 (None) 으로 놔둡니다.)


두번째. Trie 구현

1. insert(string)

트라이에 문자열 삽입

2. search(string)

주어진 단어 string이 트라이에 존재하는지 여부 반환

3. starts_with(prefix)

주어진 prefix 로 시작하는 단어들을 BFS로 트라이에서 찾아 리스트 형태로 반환

마지막 글자 flag 를 boolean 으로 안하고 data 필드로 한 이유가 바로 이 메소드 때문인데요... 잘 생각해보세요. BFS 로 단어들을 찾을 때 결국 마지막에 우리에게 반환되는 것은 Terminal 노드, 즉 마지막 글자입니다. 그래서 단어 자체를 알려면 BFS 경로를 역추적해야 합니다... 이 과정이 귀찮기 때문에 ㅋㅋ Terminal 노드만 찾으면 BFS 역추적 할 필요 없이 단어가 뭔지 알 수 있도록 data 필드에 전체 단어를 넣어 놓은 것이죠.


위 세 가지만 구현하면 됩니다! 아래는 제가 간단히 파이썬으로 구현해본 Trie 입니다.

(파이썬 전체 코드는 여기를 클릭하면 보실 수 있습니다.)


끝!!

학교 자료구조 수업에서는 비중이 많이 있는 놈은 아니지만, 기술 면접이나 코딩 대회에서 많이 다루어진다고 하니 열심히 공부합시다!! 우리의 핵심 목표는 Trie다 하는 것으로 정신을 차리고 나아가면 취직할 수 있는 에너지가 분산되어 우주가 나서서 도와준다는 그런 마음을 가질 수 있을거다, 그렇게 생각합니다.

리스트 (List) - 1. ArrayList 구현

자료구조

10일간의 추석 연휴 오예 신난다 동안 뭐를 할지 고민하다가 평소에 하겠다고 다짐만 하고 막상 하지는 못 했던 자료 구조 정리를 해보려고 합니다. 특히 제가 내년 초에 있을 기술 면접 대비도 해야 하기 때문에 기술 면접에서는 어떻게 등장할 수 있을지도 초점을 맞춰서 써보도록 하려고요. 제가 많이 부족하지만 벼락치기 대비에 유용한 가이드가 되었으면 좋겠습니다.


리스트

[정의] 순서가 있는 원소들의 집합 (An ordered collection of elements)

맨 처음으로 다룰 자료 구조는 리스트 추상 자료형(Abstract Data Type, ADT) 입니다.

여담: 순서가 없는 원소들의 집합은 Set! ㅎㅎ


대표적인 연산 종류

1. list()

생성자 constructor 입니다. 빈 리스트를 생성합니다.

필드에는 

(1) Object[] items (리스트 원소들의 array)

(2) int numItems (원소의 개수)

가 있습니다.

2. void add(Object ob)

리스트의 끝에 ob 라는 Object 를 추가합니다.

3. void add(int pos, Object ob)

리스트의 pos 위치에 ob 라는 Object 를 추가합니다. 

*** 이 과정에서 원래 pos 위치에 있던 원소부터 size() 위치(맨 끝)에 있던 원소들은 ob 를 위한 공간을 만들어주기 위해 한 칸씩 오른쪽으로 이동하겠죠?

(단, pos0보다 작거나 size() 보다 크면 에러)

4. boolean contains(Object ob)

ob 라는 Object 가 리스트에 있다면 true 를 반환합니다.  

5. int size()

리스트에 있는 원소의 개를 반환합니다.

6. boolean isEmpty()

리스트가 비어있으true 를 반환합니다.

7. Object get(int pos)

pos 위치에 있는 원소를 반환합니다. 

(단, pos  0보다 작거나 pos  size()면 에러, 0-indexing 이기 때문에 pos 는 size()보다 작아야겠죠.)

8. Object remove(int pos)

pos 위치에 있는 원소를 제거한 뒤 제거된 원소를 반환합니다. 

***  과정에서 pos+1 에 위치한 원소부터 size() 에 있는 원소들은 없어진 원소 공간을 채우기 위해 한 칸씩 오른쪽으로 이동합니다. 

(단, pos 가 0보다 작거나 pos  size()면  에러, 0-indexing 이기 때문에 pos 는 size()보다 작아야겠죠.)


리스트의 구현 방법

구현 1 - ArrayList
ArrayList 는 array 를 이용한 List 구현 방법입니다. 

1. 생성자
생성자는 필드들을 initialize 해서 빈 리스트를 생성해야합니다. 원소의 개수 필드인 numItems 는 0 로 설정되야하겠고요. 원소들을 담을 array인 items 에 조금 문제가 있습니다. items 를 null 로 initialize 하자니... 나중에 메소드 쓸 때 items 가 null 인 경우를 고려해야하니 문제가 될 것 같습니다. 해답은 바로 임의의 초기 크기를 가진 array 를 만드는 겁니다. 초기 크기 INITIAL_SIZE 는 static final 필드로 정하겠습니다.

우선 10을 INITIAL_SIZE 로 정하도록 합시다. 실제 사용 시에는 어떤 상황에서 리스트가 쓰이냐에 따라 적절한 초기 크기를 정해줘야 합니다.  바로 다음에 add 메소드를 구현하면서 느끼시겠지만, 초기 크기가 크면 공간이 부족해지는 상황 전에 add 를 많이 쓸 수 있다는 장점이 있습니다. 하지만 초기 크기를 너무 크게 잡아줘서 공간을 다 쓰지도 못하고 끝나는 메모리 낭비가 될 수도 있습니다. 결국 상황에 따라 적절한 INITIAL_SIZE 를 설정하는 게 중요하겠죠.

1-a. ArrayList 생성자

2. add 메소드
우선 파라미터가 하나인 add를 구현해보도록 합니다. 간단하게 Object 를 리스트의 끝에 추가시키면 되는 메소드입니다. 그런데 여기서 중요한 문제가 하나 있어요.

"array 에 더이상 공간이 없는 경우는?"

기존 array에 더이상 새 Object 가 들어갈 공간이 없다면 어떻게 할까요? 

(1) 더 큰 array 를 만들고, 
(2) 새 array 에 원래 있던 원소들을 복사를 하고 나서야

새로운 Object 를 추가시킬 수 있을겁니다. 게다가 이 문제는 파라미터가 하나인 add(Object ob)뿐만 아니라 파라미터가 두개인 add(int pos, Object ob)에도 해당되는 문제입니다. 그렇다면 (1) - (2) 과정을 하나의 메소드로 만들어버리면 두 add에서 재활용할 수 있겠죠. 그 새로운 메소드(array 크기 확장)를 expandArray 라고 이름 짓겠습니다. 그리고 이 expandArray는 유저가 알 필요 없는, 구현을 위해서만 사용되는 메소드이기 때문에 private 메소드로 만듭니다.

2-a. add(Object ob) 와 expandArray()


*** 맨 뒤에 항목을 추가하는 add의 시간 복잡도는 O(1) 혹은 O(n) 입니다. 이게 일반적인 표기인지는 잘 모르겠습니다만... (Oracle 에서는 Amortized O(1) 이라는 표현을 쓰긴 합니다만... 일반적인 Worst Case 시간복잡도하고는 다른 개념입니다) 뒤에 항목을 추가하는 연산 자체는 O(1) 이 맞습니다. 하지만 우리가 크기를 지정해줘야하는 array를 쓰고 있어서 가끔 공간이 부족해 expandArray() 를 해줘야하는 상황이 있잖아요. 이 공간 확장의 경우 때문에 O(n) 의 상황도 생기는 것입니다.

이제 파라미터가 두 개인 add(int pos, Object ob) 의 경우를 살펴볼게요. 방금 구현한 파라미터 한 개인 add에 비해 파라미터가 하나 더 늘었다는 차이밖에 없는데요, 중요하게 점검할 부분이 있습니다.

"pos 에 올바르지 않은 값이 입력되는 경우"

pos 의 값이 올바르지 않은 경우(예를 들어 음수나 array size 보다 큰 수)에 예외처리를 해줘야합니다. 따라서 
(1) pos 가 올바른 범위에 있는지 확인합니다. 올바른 범위가 아니면 IndexOutOfBoundsException 을 throw 합니다. 
(2 pos 가 올바른 값이었다면, array 에 공간이 있는지 확인해야합니다. 공간이 없다면 expandArray() 를 호출해 array크기를 확장합니다.
(3) 그 다음, pos ~ numItems-1 까지 위치의 모든 item 들을 오른쪽으로 한 칸씩 이동시켜서 새 Object 가 들어갈 공간을 만들어줍니다. 
(4) 이 모든 과정을 한 뒤에야 새 Object 를 pos 위치에 삽입하고, numItems에 1을 더합니다.

2-b. add(int pos, Object ob)

*** 특정 위치에 항목을 추가하는 add의 시간 복잡도는 O(n) 입니다. 맨 뒤에 추가하는 add 와는 다르게, array 를 traverse 해야하기 때문이죠.



3. remove 메소드
remove 메소드 에는 지울 원소의 위치가 파라미터로 주어집니다. 그래서 
(1) 먼저 pos 가 올바른 범위에 있는지 확인을 해야합니다.
(2) void 가 아니고 지운 Object 를 반환해줘야 하기 때문에 지우기 전 지울 Object 를 임시로 저장해줘야합니다. 
(3) 그 다음 pos+1 ~ numItems-1 까지 위치의 원소들을 왼쪽으로 한 칸씩 이동해줍니다. 이 과정에서 우리가 지워야 하는 items[pos] 는 덮여쓰여지기 때문에 사실상 지워진 것이 됩니다. 
(4) 그리고 깜박할 수 있는 것 하나! 마지막 원소가 있던 원래의 자리에는 그대로 그 항목이 있습니다.

예를 들어

 pos

item 0

item 1 

item 2 

item 3

item 4 

item 5 

 value

d

e

f


와 같은 array 있을 때 item 3 을 지웠다고 합시다. 그러면 아래와 같이 한 칸씩 왼쪽으로 이동시킵니다.

 pos

item 0

item 1 

item 2 

item 3

item 4 

item 5

value

e

f

f



그런데!! 5 위치에 이동시킨 원래 항목이 그대로 남아있습니다!! 따라서 이 마지막 항목이 원래 있던 위치의 항목(이 경우 item 5)도 삭제해줘야 합니다.

(5) 그리고 나서 numItems 에서 1을 빼고, 지운 Object 를 반환해주면 되는거죠.

3-a. remove(int pos)

*** remove의 시간 복잡도는 O(n) 입니다. ob 를 위한 공간을 만들 때의 for loop 때문이죠. 

4. get 메소드

주어진 위치에 있는 항목을 반환해주면 되는데요 ㅎㅎ 쉽습니다. 
(1) pos 가 파라미터로 들어오니깐 범위 체크 해주고요, 
(2) 그 다음 items[pos] 반환해주면 끝! 

4-a. get(int pos)

get의 시간 복잡도는 O(1) 인데, 그 이유는 array 를 사용하는 것에서 찾을 수 있습니다. array access 는 메모리 시작 주소에 pos 위치를 더하기만 함으로써 access 하는 것이거든요. 결국 access = 사칙 연산이라고 볼 수 있기 때문에 O(1) 이라고 이해하는 것은 어떨까요?


5. iterator 메소드
어떤 자료 구조를 쓸 때 그 자료 구조를 iterate(순회) 할 일이 많습니다. 방금 구현한 get 메소드를 이용해서 우리의 ArrayList 를 순회하는 iterator 라는 것을 만들 수 있는데요, 중요한 포인트가 많으니 유심히 보도록 합시다. 되게 쉬운 개념인데 저는 자료 구조 수업 들을 때 신경 별로 안쓰다가 간단한 Iterator 문제에서 많이 틀렸었습니다 ㅠㅠ

자바에서 iteratorCollectionimplements 하는 모든 자료 구조에서 필요한 메소드입니다. Iterator 인터페이스는 java.util 에 정의되어 있고요, iterator 메소드는 이 Iterator 을 반환해줘야 합니다.

Iterator 은 리스트의 항목을 가리키고 있는 손가락 혹은 포인터처럼 생각하시면 쉽습니다. 

(1) 처음 Iterator 가 생성되면, 그 Iterator가장 첫번째 항목을 가리니다. 
(2) Iterator 에는 next 라는 메소드가 있는데, 이 next 라는 단어가 여러분을 혼란스럽게 할 수 있으니 조심하세요. 
(3) next 메소드는 현재 Iterator가리키고 있는 항목을 반환함과 동시에 포인터(손가락)가 다음(next) 항목을 가리키게 합니다. 절대로 다음 항목을 반환하는 게 아닌거죠... 현재 가리키고 있는 항목을 반환하는 겁니다!! next 라고 이름 붙여진 것은 호출되면 다음 항목을 가리키기 때문에 입니다.


Iterator 가 어떻게 작동하는지 예제와 함께 알아봅시다. 아래와 같은 Fruits 리스트가 있습니다.

사과 

배 

바나나 

딸기 

 


1. 이 리스트에 대한 Iterator 을 생성하면, Iterator 은 아래처럼 맨 처음 항목인 사과를 가리키게 됩니다.

사과 

배 

바나나 

딸기 

 

 


 


 

2. 이제 next 를 호출하면 현재 가리키고 있는 사과를 반환하고, 리스트의 Iterator 은 아래처럼 다음 항목인 배를 가리키게 됩니다.

사과 

배 

바나나 

딸기 

 

 

 

 


 

3. next 를 호출 -> 배를 반환.  포인터는 바나나를 가리킴.

사과 

배 

바나나 

딸기 

 

 

 

 


 

4. next 를 호출 -> 바나나를 반환.  포인터는 딸기를 가리킴.

사과 

배 

바나나 

딸기 

 

 

 

 

 
5. (주의) 위와 같은 상황의 Iterator 의 hasNext 메소드는 true 를 반환합니다! 왜? 아직 access 하지 못한 항목이 하나 남았잖아요. 다시 한번 next 를 호출하면 딸기를 반환할 것이고 그제야 아래와 같은 그림이 됩니다.

사과 

배 

바나나 

딸기 

 

 

 

 


 

6. 이제 iterator 가 리스트의 바깥으로 나가버렸습니다. 이제 hasNext 메서드는 false 를 반환하고요, 이 상황에서 next 를 호출하면 NoSuchElementException 응~그런거없어 에러를 뿜는 걸 볼 수 있을겁니다.



아래는 우리 List 클래스를 위한 Iterator 을 구현에 대한 설명입니다.


우선 ListIterator 라는 새로운 클래스를 만들건데요, 두 가지 필드가 있습니다. 

(1) iterate(순회) 될 List

(2) 포인터(손가락) -- 인덱스라고 합시다 ㅎㅎ


그리고 우리의 ArrayList 클래스에서는 아래처럼 iterator 라는 메소드를 만들어줘야 합니다. 이 메소드는 ListIterator 의 생성자를 호출해 자기 자신을 List 에 반환합니다.


아까 Iterator 라는 인터페이스가 있다고 말씀드린 거 기억 나세요? ListIterator 은 이 인터페이스를 implements 하기 때문에 세 가지 메소드를 구현해야합니다. 아까 봤던 hasNext 와 next, 그리고 선택적으로 remove 라는 메소드를 구현해야 합니다. 아래에 간단히 구현한 ListIterator 클래스를 참고해주세요.


6. contains 메소드
contains 는 파라미터로 들어온 Object 가 List 가 존재하면 true 를 반환합니다. items 를 순회하며 원하는 Object 가 있는지 비교해가며 체크하면 됩니다. 아래 구현을 보시죠.

7. isEmpty 메소드
ㅎㅎ 이제 막판이네요. isEmpty 는 List 가 비어있는지 여부를 반환합니다. 즉 List 원소 개수가 0이면 true 를 반환합니다.

8. size 메소드
size 는 List 원소 개수를 반환합니다. 지금까지 많이 호출했던 메소드인데 ㅋㅋ 이제야 구현하는군요.


구현 2 - LinkedList


이번 글에서는 array 를 이용한 List 구현인 ArrayList 를 알아봤는데요, LinkedList 라는 구현 방법도 있습니다. 다음 편에서 알아보도록 하겠습니다.



[알고리즘] 너비 우선 탐색(Breadth First Search)과 구현 방법

자료구조

이 글에서는 트리나 그래프를 순회(traverse)/탐색(search)하는 알고리즘 중에 하나인 너비 우선 탐색 (Breadth First Search, BFS) 에 대해 다룹니다. 깊이 우선 탐색에 대해서는 아래 글을 참고해주세요 


2016/07/05 - [자료구조] - [알고리즘] 깊이 우선 탐색(Depth First Search)과 구현 방법


그래프 탐색의 필요성 이미 DFS 에 대한 제 글을 읽으셨다면 그래프 탐색의 필요성을 넘어가시면 됩니다. ^ㅍ^


 

사진 출처: http://pages.cs.wisc.edu/~paton/readings/Graphs/


그래프 자료구조라고 하면 어떤 것이 생각나시나요? 위와 같이 아기자기한 그림인가요? 


하지만 아래를 보면 어떠신가요?


자료 구조 설명하다가 무슨 삼성 그룹의 순환 출자에 대한 그림을 가져왔냐고 화를 내실지도 모르겠습니다만 꼭짓점(vertex)이 수없이 많은 그래프라고 생각해보세요. 이 모든 꼭짓점을 빠짐없이 방문하려면 어떻게 해야할까요? 선형구조인 단순한 리스트(List) 였다면 리스트의 총 원소 개수 N을 구해서 0~ N 까지 위치의 원소를 출력하면 탐색 완료지만, 그래프에서는 노드에 순서대로 번호가 있는 것도 아니고 하기 때문에 모든 원소에 대한 탐색이 어려운 것입니다. 이 난관을 극복하기위해 DFS 같은 알고리즘이 필요한 것이죠.


기본 원리

아래 두 사진 출처: CS188: Artificial Intelligence, UC Berkeley (강의 슬라이드)





위에 그림처럼 산과 그 속에 묻힌 보석을 찾아야하는 로봇이 있습니다. 로봇은 보석을 찾기 위해 첫번째 그림처럼 한없이 밑으로 내려가볼 수도 있고, 두번째 그림처럼 정상부터 점점 내려오면서 높이 별로 찾아볼 수도 있을겁니다. 전자와 같은 방식을 깊이 우선 탐색이라고 하고요, 후자가 오늘 설명할 너비 우선 탐색 (Breadth First Search, BFS) 라고 합니다. 둘은 산 속에 숨겨진 보석을 찾는다는 목표는 같지만, 그 찾는 순서가 다릅니다. 


산이 2000m 라고 할 때, BFS는 2000m -> 1900m 훑고 -> 1800m 훑고 -> ... -> 100m ~ 0m 까지 훑어서 탐색하는 것이죠. 좀 더 정의에 관련해서 설명하자면, 시작점 (2000m) 에서 같은 거리에 있는 원소들을 다 훑어야만 그 거리보다 더 먼 곳 (1900m~0m) 으로 차례차례 진격할 수 있는 것입니다.



가족 관계를 예로 들어 설명해보겠습니다. 자 오늘은 추석입니다~ 우리 민족의 대명절 추석에 아차! 일이 생겨 가족 모임에 가지 못하게 됐습니다. 저는 가족 관계를 원만하게 하는 것을 미덕으로 생각하는 사람이라서 8촌 이내의 모든 가족에게 빠짐 없이 연락하고 싶습니다. BFS 의 방식으로 연락을 한다면 어떻게 되는걸까요? 먼저 1촌인 부모님과 자녀에게 연락을 합니다. 그다음에 2촌인 가족들에게 연락을 돌리고요, 계속해서 3, 4, ... 8촌 까지 연락을 하면 모든 가족에게 빠짐없이 연락한 것이 됩니다. 이러한 순서로 그래프를 탐색하는 것이 BFS 입니다.



귀여운 그림을 사용해서 설명을 해봤는데 실제 그래프를 통해 BFS 가 어떻게 이루어지는지 아래에서 살펴봅시다.



BFS의 방문 순서

사진 출처: https://en.wikipedia.org/wiki/Breadth-first_search


맨 위를 첫 번째 단(Tier 1)이라고 하고 그 뒤로 두 번째 단, ... 이어진다고 합시다. 먼저 첫번째 단의 원소인 1 을 찍고 갑니다 (방문visit합니다). 그 다음 두번째 단에는 원소들을 전부 찍고, 세번째 단도 전부 찍고,... 단(Tier) 별로 방문하는 것을 볼 수 있습니다. 각 노드 안의 숫자는 방문 순서를 나타냅니다.



파이썬으로 구현하기

이제 BFS 를 실제 코드로 구현해보도록 합시다. BFS 에서 중요한 요소는 바로 큐 (Queue) 자료 구조입니다. 


좀 흥미로운 그래프를 가져왔습니다. 우리나라 정부 청사들이 다 세종시로 옮겨가는 중인데요, 세종시에서 BFS 를 통해 우리나라의 주요 장소를 (평양까지...!!ㅋㅋㅋ) 순회해보겠습니다.


순회 과정을 아래에 차근 차근 표현해 놓았으니, 아래 그래프를 새 창에 열어놓고 과정을 천천히 따라가보세요.



1. 먼저 Queue 에 시작점인 세종시를 넣습니다. 


그 다음, 큐의 맨 앞에 있는 세종을 불러서Queue.dequeue() 방문visit합니다. 세종시에 이어진 서울, 강릉, 대구, 광주을 큐에 줄세웁니다Queue.enqueue(세종의 자손 노드들) . 


>> 큐의 뒤

IN 

(enqueue)

  

 광주

대구

강릉

울 

세종 (Visit)

 >> 큐의 앞

OUT

(dequeue)

방문한 곳: {세종, }


2. 큐의 맨 앞에 있는 서울을 큐에서 내보내고 방문합니다. 서울시에 이어진 평양, 인천을 큐에 줄세웁니다Queue.enqueue(서울의 자손 노드들) . 단, 세종은 이미 방문했으므로 제외합니다.


>> 큐의 뒤

IN 

 

 

인천 

 

광주

대구

강릉

서울 (Visit)

 >> 큐의 앞

OUT

방문한 곳: {세종, 서울, }


3. 큐의 맨 앞에 있는 강릉을 큐에서 내보내고 방문합니다. 강릉시에 이어진 독도를 큐에 줄세웁니다Queue.enqueue(강릉의 자손 노드들) . 단, 세종은 이미 방문했으므로 제외합니다.


>> 큐의 뒤

IN 

 

독도 

 인천

평양

광주

대구

강릉 (Visit)

 >> 큐의 앞

OUT

방문한 곳: {세종, 서울, 강릉, }


4. 큐의 맨 앞에 있는 대구를 큐에서 내보내고 방문합니다. 대구시에 이어진 울산을 큐에 줄세웁니다Queue.enqueue(대구의 자손 노드들) . 단, 세종은 이미 방문했으므로 제외합니다.


>> 큐의 뒤

IN  

 

 울산

독도 

 인천

평양

광주

대구 (Visit)

 >> 큐의 앞

OUT

방문한 곳: {세종, 서울, 강릉, 대구, }


5. 큐의 맨 앞에 있는 광주를 큐에서 내보내고 방문합니다. 광주시에 이어진 여수를 큐에 줄세웁니다Queue.enqueue(광주의 자손 노드들) . 단, 세종은 이미 방문했으므로 제외합니다.


>> 큐의 뒤

IN  

 

여수

 울산

독도 

 인천

평양

광주 (Visit)

 >> 큐의 앞

OUT

방문한 곳: {세종, 서울, 강릉, 대구, 광주, }


6. 큐의 맨 앞에 있는 평양을 큐에서 내보내고 방문합니다. 평양시에 이어진 서울은 이미 방문했네요. Queue.dequeue()  하고 평양 visit만 한 채로 다음 단계로 갑니다.


>> 큐의 뒤

IN  

 

 

 여수

 울산

독도 

 인천

평양 (Visit)

 >> 큐의 앞

OUT

방문한 곳: {세종, 서울, 강릉, 대구, 광주, 평양, }


7. 큐의 맨 앞에 있는 인천을 큐에서 내보내고 방문합니다. 인천시에 이어진 서울은 이미 방문했네요. Queue.dequeue()  하고 인천 visit만 한 채로 다음 단계로 갑니다.


>> 큐의 뒤

IN  

  

 

 여수

 울산

독도 

인천 (Visit)

 >> 큐의 앞

OUT

방문한 곳: {세종, 서울, 강릉, 대구, 광주, 평양, 인천, }


8. 큐의 맨 앞에 있는 독도을 불러서 방문합니다. 독도에 이어진 강릉은 이미 방문했네요. Queue.dequeue()  하고 독도 visit만 한 채로 다음 단계로 갑니다.


>> 큐의 뒤

IN  

   

 

 여수

 울산

독도 (Visit)

 >> 큐의 앞

OUT

방문한 곳: {세종, 서울, 강릉, 대구, 광주, 평양, 인천, 독도, }



9. 큐의 맨 앞에 있는 울산을 큐에서 내보내고 방문합니다. 울산시에 이어진 부산을 큐에 줄세웁니다Queue.enqueue(울산의 자손 노드들) . 단, 대구는 이미 방문했으므로 제외합니다.


>> 큐의 뒤

IN  

    

 부산

 여수

울산 (Visit)

 >> 큐의 앞

OUT

방문한 곳: {세종, 서울, 강릉, 대구, 광주, 평양, 인천, 독도, 울산, }


9. 큐의 맨 앞에 있는 여수를 큐에서 내보내고 방문합니다. 여수시에 이어진 부산을 큐에 줄세웁니다Queue.enqueue(여수의 자손 노드들) . 단, 광주는 이미 방문했으므로 제외합니다.


>> 큐의 뒤

IN  

    

 부산

 부산

여수 (Visit)

 >> 큐의 앞

OUT

방문한 곳: {세종, 서울, 강릉, 대구, 광주, 평양, 인천, 독도, 울산, 여수, }


10. 큐의 맨 앞에 있는 부산을 큐에서 내보내고 방문합니다. 부산시에 이어진 여수, 울산은 모두 이미 방문했으므로 부산 visit 만 한 채로 다음 단계로 갑니다.


>> 큐의 뒤

IN  

    


 부산

부산 (Visit)

 >> 큐의 앞

나가는 방향

방문한 곳: {세종, 서울, 강릉, 대구, 광주, 평양, 인천, 독도, 울산, 여수, 부산, }



11. 마지막으로 큐에 남아있는 부산은 이미 방문되어 있으므로 큐에서 내보냅니다. 그 뒤에 큐에 남은 장소가 없으므로 BFS 탐색이 끝났습니다.


>> 큐의 뒤

IN  

    


 

부산 (이미 방문)

 >> 큐의 앞

나가는 방향

방문한 곳: {세종, 서울, 강릉, 대구, 광주, 평양, 인천, 독도, 울산, 여수, 부산, }


결과를 보니깐 11개 장소를 빠짐 없이 방문한 것을 볼 수 있습니다. 오예!


 

이 긴 과정을 파이썬 코드로 나타내보겠습니다. 


그래프는 파이썬에서 다음과 같이 나타낼 수 있겠습니다.

 
korea = {'세종': set(['서울', '강릉', '대구', '광주']),
         '서울': set(['평양', '인천', '세종']),
         '강릉': set(['독도', '세종']),
         '광주': set(['세종', '여수']),
         '대구': set(['세종', '울산']),
         '평양': set(['서울', ]),
         '인천': set(['서울', ]),
         '독도': set(['강릉', ]),
         '여수': set(['광주', '부산']),
         '울산': set(['대구', '부산']),
         '부산': set(['여수', '울산']),
         }


아래가 bfs 함수입니다.

 
def bfs(graph, root):
	visited = [] # 방문한 곳을 기록
	queue = [root] # 큐에 시작점을 줄세움

	while queue: # queue 가 빌 때 까지 탐색을 계속
		vertex = queue.pop(0) # 큐의 맨 앞의 원소를 방문할 꼭짓점으로 설정

		if vertex not in visited: # 꼭짓점이 방문된 적이 없다면 방문 기록에 추가
			visited.append(vertex)
			for node in graph[vertex]: # 꼭짓점에 연결된 노드들 중 
				if node not in visited: # 방문 안 된 곳 만을
					queue.append(node) # 큐에 줄세움

	return visited

##### 실행결과 #####
print(bfs(korea, '세종'))
>>> ['세종', '서울', '대구', '강릉', '광주', '인천', '평양', '울산', '독도', '여수', '부산']




BFS 경로탐색


방문 순서를 기록하면서 재귀 호출을 이용하면 아래와 같이 부산에서 평양까지의 경로 탐색도 할 수 있습니다. 


paths = [] def bfs_paths(graph, start, end, path=[]): # 그전 방문했던 노드들 유지. 이번 차례 방문하는 꼭짓점도 visited에 추가 path = path + [start] # 목적지에 도달했으면 paths 에 경로 기록 후 종료 if start == end: paths.append(path) # bfs 와 같음 queue = [start] while queue: vertex = queue.pop(0) for node in graph[vertex]: if node not in path: # 방문하지 않은 자손들에 대해 쭈우욱 재귀 호출 BFS_paths(graph, node, end, path) ##### 실행결과 ##### bfs_paths(korea, '부산', '평양') print(paths) >>> [['부산', '울산', '대구', '세종', '서울', '평양'], ['부산', '여수', '광주', '세종', '서울', '평양']]


참고 자료


[알고리즘] 깊이 우선 탐색(Depth First Search)과 구현 방법

자료구조

이 글에서는 트리나 그래프를 순회(traverse)/탐색(search)하는 알고리즘 중에 하나인 깊이 우선 탐색 (Depth First Search, DFS) 에 대해 다룹니다.  너비 우선 탐색에 대해서는 아래 글을 참고해주세요  


2016/07/05 - [자료구조] - [알고리즘] 너비 우선 탐색(Breadth First Search)과 구현 방법



그래프 탐색의 필요성이미 BFS 에 대한 제 글을 읽으셨다면 그래프 탐색의 필요성을 넘어가시면 됩니다. ^ㅍ^


 

사진 출처: http://pages.cs.wisc.edu/~paton/readings/Graphs/


그래프 자료구조라고 하면 어떤 것이 생각나시나요? 위와 같이 아기자기한 그림인가요? 


하지만 아래를 보면 어떠신가요?

사진 출처: 오마이뉴스


자료 구조 설명하다가 무슨 삼성 그룹의 순환 출자에 대한 그림을 가져왔냐고 화를 내실지도 모르겠습니다만 꼭짓점(vertex)이 수없이 많은 그래프라고 생각해보세요. 이 모든 꼭짓점을 빠짐없이 방문하려면 어떻게 해야할까요? 선형구조인 단순한 리스트(List) 였다면 리스트의 총 원소 개수 N을 구해서 0~ N 까지 위치의 원소를 출력하면 탐색 완료지만, 그래프에서는 노드에 순서대로 번호가 있는 것도 아니고 하기 때문에 모든 원소에 대한 탐색이 어려운 것입니다. 이 난관을 극복하기위해 DFS 같은 알고리즘이 필요한 것이죠.



기본 원리

아래 두 사진 출처: CS188: Artificial Intelligence, UC Berkeley (강의 슬라이드)

깊이 우선 탐색



너비 우선 탐색



위에 그림처럼 산과 그 속에 묻힌 보석을 찾아야하는 로봇이 있습니다. 로봇은 보석을 찾기 위해 첫번째 그림처럼 한없이 밑으로 내려가볼 수도 있고, 두번째 그림처럼 정상부터 점점 내려오면서 높이 별로 찾아볼 수도 있을겁니다. 전자와 같은 방식을 오늘 설명할 깊이 우선 탐색이라고 하고요, 후자는 너비 우선 탐색 (Breadth First Search, BFS) 라고 합니다. 둘은 산 속에 숨겨진 보석을 찾는다는 목표는 같지만, 그 찾는 순서가 다릅니다.


오늘 설명할 DFS 는 한 번 판곳은 땅바닥이 나올 때까지 죽도록 팝니다. 식물 뿌리를 생각해볼까요? 


이 식물의 뿌리는 네 방향으로 나뉘어집니다. 제가 각각 1, 2, 3, 4로 표시 했습니다.

이제 로봇이 1로 탐색하려고 들어갔다고 한다면... DFS 에 따르면 1의 줄기인 a, b, c 를 모두 다 찍고 가야합니다. 

마찬가지로 그 다음에 2에 들어갔다면 2에 연결 된 줄기 모두를 찍어야 3이나 4로 넘어갈 수 있는 거지요.



마침 엉덩국 씨의 유명한 짤이 생각나서 넣어봤습니다.


 한 곳을 팠을 때는 마음대로였겠지만, 나갈때는 아니란다! DFS 는 팠으면 끝까지 파고 난 다음에야 나갈 수 있는 것입니다.


귀여운 그림을 사용해서 설명을 해봤는데 실제 그래프를 통해 DFS 가 어떻게 이루어지는지 아래에서 살펴봅시다.


DFS의 방문 순서

1. 맨 위 root node (1) 에서 탐색이 시작한다고 가정.
2. 좌우 노드 중 왼쪽 노드를 항상 우선 탐색한다고 가정.
사진 출처: http://docs.seqan.de/seqan/1.2/streePreorder.png



위 그림에서 각 꼭짓점 안의 숫자는 방문 순서를 의미합니다. 맨 위 뿌리 노드에서 시작합니다. 가정에 따라 맨 왼쪽으로 가네요... 그리고 한없이 밑으로 갑니다. 왼쪽 3으로 갔다가 4로 가서 5, 6까지 내려갑니다. 다음, 현재 방문하지 않은 꼭짓점 중 가장 왼쪽이면서 위쪽에 있는 노드인 7로 갑니다. 그 뒤로는 위 그림의 방문 순서를 스스로 따라가보시기를 권합니다. 


파이썬으로 구현하기

제가 요즘 열심히 공부하는 Python 으로 DFS 를 구현해보고자 합니다. 중요한 점: DFS 를 구현할 때는 스택을 이용하는데, 그 이유를 아래 그림과 함께 보시죠.

사진 출처: https://en.wikipedia.org/wiki/Depth-first_search

 순서

(방문하고 있는)

꼭짓점

자손

 스택 

(빨간색 = 스택의 맨 위)

 1

 

 

   A

 2

 A (시작점)

 B, C, E

  B, C, E

 3

 B

 D, F

  D, F, C, E 

 4

 D

 없음

  F, C, E 

 5

 F

 E

  E, C, E 

 6

 E

 A (이미 방문)

   C, E 

 7

 C

 G

   G, E 

 8

 G 없음

  E (이미 방문)

 9

 스택이 비면 탐색 종료






1. 스택에 처음 시작점을 넣습니다stack.push(A).

2. 스택의 맨 위 원소를 빼낸stack.pop() (A) 가 현재 방문하고 있는 꼭짓점이 됩니다. 그 꼭짓점의 자손들 (B, C, E) 를 스택에 밀어 넣습니다stack.push(B, C, E).

3. 또 다시 stack.pop() (B) 를 방문합니다. 그 다음 B의 자손들 (D, F) 를 스택에 밀어 넣습니다stack.push(D, F).

4. stack.pop() (D) 를 방문합니다. D 의 자손은 없으니 다음 순서로 넘어갑니다.

5. stack.pop() (F) 를 방문합니다. F 의 자손(E) 를 스택에 밀어 넣습니다stack.push(E).

6. stack.pop() (E) 를 방문합니다. E 의 자손(A) 를 스택에 밀어 넣으려고 보니 이미 방문한 점이네요. 넣지 않고 다음 순서로 넘어갑니다.

7. stack.pop() (G) 를 방문합니다. G 의 자손은 없으니 다음 순서로 넘어갑니다.

8. stack.pop() 하니깐 이미 방문한 E가 나오네요. 다음 순서로 넘어갑니다.

9. 더이상 stack 에 남아있는 꼭짓점이 없습니다. 탐색을 종료합니다.



pseudo-code 로 DFS 과정을 대략 짜보겠습니다.

 
function DFS(Graph graph, Node root)
	Stack stack // Stack 선언

	stack.push(root)

	while 스택에 원소가 있을 동안 do
		방문할 꼭짓점 V = stack.pop() // 스택 맨 위의 원소를 꺼내서
		V.visit() // 방문
		stack.push(V 의 자손 노드들 *단, 이미 방문한 노드는 제외) // 방문한 노드의 자손 노드들을 스택에 push.
	end


자 이제 파이썬으로 코딩하기 전에, Graph 를 표현해야겠죠.


파이썬에서 Graph 는 아래 같이 원소와 연결된 원소들의 set 을 대응시킨 dictionary 자료형으로 표현할 수 있습니다. (Python Patterns - Implementing Graphs | Python.org)

#파이썬에서 위 그래프 표현
graph = {'A': set(['B', 'C', 'E']),
         'B': set(['A', 'D', 'F']),
         'C': set(['A', 'G']),
         'D': set(['B']),
         'E': set(['A', 'F']),
         'F': set(['B', 'E']),
         'G': set(['G'])}


자 그러면 DFS 를 구현해봅시다. 

def dfs(graph, root):
	visited = [] # 각 꼭짓점(vertex)이 방문되었는지 기록
	stack = [root, ] 

	while stack: # stack 이 비게 되면 탐색 끝
		vertex = stack.pop() # 방문되어지고 있는 꼭짓점
		if vertex not in visited: # 
			visited.add(vertex)
			stack.extend(graph[vertex] - visited)

	return visited;

########### 실행 결과 ###########
print(dfs(graph, 'A'))
>>> {'F', 'B', 'A', 'E'}

참고로 DFS 는 그래프에서 모든 꼭짓점을 찾아가는 과정이라고 생각하세요. dfs(graph, 'A') 의 결과가 저와 순서가 다른 것은 당연합니다. visited 는 순서가 없는 list 자료형이니까요. 중요한 것은 dfs 를 통해 모든 꼭짓점을 찾았느냐입니다.


이 DFS 를 재귀적으로(recursive) 구현도 합니다. 좀 더 깔끔해 보이는 장점이 있는데, 아래 코드를 함께 보시죠.

def dfs_recursive(graph, root, visited=None):
	if visited is None:
		visited = set()

	visited.add(root)

	# 주어진 root 과 연결되어 있는 다른 node 들에 대해 방문하지 않은 것들만 재귀 호출합니다.
	for node in graph[root] - visited:
			dfs_recursive(graph, node, visited)

	return visited



DFS 경로 탐색


그렇다면 DFS 로 A 부터 F 까지 가는 경로를 탐색해볼까요? 앞의 dfs 함수와는 달리 방문 순서를 순서대로 기록할 필요가 있다는 것만 기억하시면 되겠습니다.

 

paths = []

def dfs_paths(graph, start, end, visited=[]):
	# 그전 방문했던 노드들 유지. 이번 차례 방문하는 꼭짓점도 visited에 추가
	visited = visited + [start]

	# 도착했으면 paths 에 경로 기록하고 종료
	if start == end:
		paths.append(visited)

	# 현재 점의 자손 노드 중에 방문하지 않은 노드에 대해 재귀 호출
	for node in graph[start]:
		if node not in visited:
			dfs_paths(graph, node, end, visited)


########### 실행 결과 ###########
dfs_paths(graph, 'A', 'F')
print(paths)
>>> [['A', 'C', 'F'], ['A', 'B', 'E', 'F']]



다음에는 너비 우선 탐색에 대해 다뤄보도록 하겠습니다.



참고 자료

http://pages.cs.wisc.edu/~paton/readings/Graphs/

Depth-First Search and Breadth-First Search in Python - Edd Mann