항해99 Weekly I learned 3주차 <알고리즘 편> <DFS, BFS>

김효진·2022년 1월 30일

탐색 알고리즘과 자료구조(Dfs, Bfs)

깊이 우선 탐색(dfs), 너비 우선 탐색(bfs) 등 알고리즘을 구현하는 것이 아직까지도 어떤 문제를 마주할때면 어떤 방식으로 접근해야 될지를 많은 고민을 하게 만든다. 조금 더 나아가 어떻게하면 이러한 문제를 조금이라도 나아지게 할 수 있을까 고민을 하면서 찾아본 결과, 난 트리라는 게 어디에 쓰이는 것인지, 그리고 트리에서 탐색을 한다는 것 자체가 무슨 의미가 있는 것인지를 완벽하게 알지 못하고 쓰고 있기 때문은 아닐까 생각이 들었다. 그래서 나는 탐색이 뭔지 써보려고 한다.

탐색은 도대체 무엇이며, 왜 하는 걸까?

자료 탐색이란, 아주 방대한 자료들이 쌓여 있을 때 우리가 원하는 자료를 찾는 작업을 말합니다. 예를 들어 테이터가 아주 많은 고객 데이터베이스에서 원하는 유저의 정보를 찾아 보여주고 싶을 때도 쓰이고, 구글에서 검색어를 쳤을 때 구글 데이터베이스에 쌓여있는 모든 관련 링크 또는 자료 중 관련된 것들을 찾아서 보여줄 때도 쓰이죠.

그냥 찾으면 되는 거지, 거기에 알고리즘이 대체 왜 필요해?라고 생각할 수도 있지만, 도서관을 생각해볼까요? 그 산더미같은 책 무덤에서 우리가 원하는 책 한 권을 잘 찾으려면 잘 짜인 <정리체계>가 필요하다는 것을 생각하면 조금은 와 닿을까요?

이렇게 모든 책들이 카테고리별로 잘 분류되어 있고, 그 안에서도 ㄱ,ㄴ,ㄷ 순으로 잘 정리되어 있다면 (이렇게 분류하고 정리하는 작업은 "정렬 알고리즘"으로 처리되겠죠?!), 우리는 원하는 책을 찾기 위해 할 일은 단순히 어떤 카테고리인지 확인한 후, 그 안에서 ㄱ,ㄴ,ㄷ 순으로 책을 찾아나가는 것입니다. 이 모든 과정이 바로 탐색 알고리즘의 과정인거죠!

하지만 만약 책을 저렇게 잘 분류 해놓지 않은 도서관이라면 얘기가 달라져요. 우리가 모든 책들을 하나하나 직접 확인해 가면서 원하는 책을 찾아야 할테니까요.

이렇게 무식하고 원초적인 방법이 바로! 깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS)입니다.
두 탐색 알고리즘은 탐색을 어떤 순서로 하느냐만 살짝 다를 뿐, 어떤 효율성도 생각하지 않고 모든 자료를 하나하나 다 확인해 본다는 점은 똑같습니다. 우리가 탐색 알고리즘을 배울 때 가장 기본 알고리즘으로 제일 먼저 배우지만, 현실에서는 절대 쓰이지 않는 이유도 여기에 있죠.

바로, 너무 무식해서!!

인간은 시간과 자원을 (너무나) 아끼고 싶어하기 때문에 실제로 자료를 탐색해야 할 때는 절대 모든 것들을 하나하나 탐색하지 않습니다. 조금 더 빨리 탐색할 수 있는 방법이 꾸준히 제안되며 훨씬 효율적인 알고리즘들이 많이 개발되었는데, 먼저 DFS와 BFS를 알아보는 시간을 갖겠습니다.

탐색이 필요한 또 다른 세계, Game

자료 탐색에 대해 길게 설명했는데, 사실 탐색 알고리즘은 꼭 자료를 찾는 것이 아닌 상황에서도 요긴하게 쓰일 때가 많습니다. 그중 하나가 바로 게임이죠!

바둑 하는 인골지능, 알파고를 기억하시나요? 1996년, 체스가 인공지능에게 정복 된 이후로도 꽤 오랫동안 바둑은 절대 넘지 못할 산으로 여겨졌습니다. 바로 체스를 훨씬 능가하는 경우의 수 때문이었죠. 일단 8 x 8로 총 64칸에서 이루어지는 체스판 개수로만 비교해도 바둑은 19 x 19 로 361개의 점이 있으니 큰 차이가 나고... 모든 경우의 수를 다 계산하자면 어마어마하게 큰 숫자가 됩니다.

이렇게 엄청난 알파고를 개발한 딥마인드 팀은 알파고에 쓰인 알고리즘 중 몬테카를로 트리 탐색 알고리즘이 있다고 밝혔습니다.
뭔지는 몰라도, 여기에 "탐색 알고리즘"이 있네요! 알파고가 바둑을 할 때 탐색 알고리즘은 왜 필요한 걸까요?

바둑은 수읽기가 중요한 게임입니다. 내가 돌을 내려놓을 수 있는 곳, 그리고 상대가 내려놓을 법한 곳들을 더 많이, 더 먼 미래의 수들까지 예측할 수록 게임에서 유리해지죠. 물론 모든 수를 다 읽을 수 있다면 승률은 100%가 될 것입니다. (하지만, 바둑에서 나올 수 있는 모든 경우의 수는 우주의 원자 개수보다 많다고 알려져있죠.ㅎㅎ..)

여기서 바로 탐색이 사용됩니다.
예를 들어 현재 200개의 점이 남았다면 그 중 한 점에 놓아보고, 그 다음 상대의 돌을 예측해보고, 별로라면 다시 다른 점에 놓아보고,... 이렇게 여러가지로 진행될 수 있는 게임 과정을 머릿속(또는 알파고라면 메로리)에서 반복하면서 최적의 수를 찾기 위해 여러 경우의 수들을 "탐색"하는거죠.

자료 탐색이 아닌 게임에서도 경우의 수들을 확인한 후 어떤 것이 최적인지 알아내기 위해 탐색이 쓰인다고 하니, 어떻게 쓰이는지 직접 확인해보지 않을 수 없겠죠! 다음 글에서는 탐색이 쓰일 수 있는 여러 게임 중 8-Puzzle과 미로찾기 두 가지 간단한 문제의 알고리즘을 직접 구현하고 결과를 확인해 보겠습니다.

우리가 직접 경험한 탐색 알고리즘

그렇다면, 혹시 우리가 실생활에 탐색 알고리즘을 써 본 적은 없을까요? 좀 더 와 닿는 사례를 들어보죠!

바둑 또는 다른 게임을 하면서 여러가지 경우의 수가 존재할 때, 가장 좋은 선택을 하기 위해 모든 경우의 수들을 메모지에 적어본 경험이 있나요? 아니, 만약 머리가 좋은 사람이라면 여러가지 경우의 수들을 다 머릿속에 기억해 두면서 몇 수 앞을 따져본 적이 있을 수도 있구요!

그런 적이 있다면, (없더라도 같이 상상해보죠!) 혹시 그 경우의 수들을 좀 더 체계적으로 따져 보기 위해서
1) 한 단계를 진행할 때 가능한 경우의 수를 전부 써보고, 각각에 대해서 또
2) 두단계를 진행할 때 가능한 경우의 수를 써보면서 따져본 적이 있나요? 마치 나무에서 가지가 자라듯이 엄청나게 다양한 경우의 수가 막 퍼져나가는 그 그림이요!

이런 그림을 그려본 경험이 있다면 당신은 이미 "탐색 알고리즘"을 직접 실행해 본 적이 있는 겁니다!(그런 경험이 없더라도 상상할 수 있다면 해봅시다!)
탐색에 쓰인다는 트리도 활용하면서요! (저 그림 자체가 트리입니다.)

만약 아래 그림처럼,
1) 한 단계 진행 시 가능한 경우의 수,
2) 두 단계 진행 시 가능한 경우의 수
와 같이 매 단계에서 가능한 경우의 수들을 모두 확인하며 탐색한다면 그것이 바로 너비 우선 탐색(BFS)입니다. 간단하죠?! 너비 우선 탐색은 이렇게 트리를 넓히면서 탐색하는 알고리즘입니다.

반면, 깊이 우선 탐색(DFS)은
1) 여러 경우의 수 중 하나를 선택
2) 선택 후 가능한 여러 경우의 수 중 또 하나를 선택
하는 식으로 매 단계에서 가능한 것 중 일단 하나를 선택해 끝을 볼 때까지 깊게 들어갑니다. 한 우물한 파서 끝에 도달했는데도 원하는 답이 안나왔다면, 그 직전으로 돌아갔다가 다시 또다른 끝을 확인합니다. 이러한 과정을 원하는 결과가 나올 때까지 반복하죠.

너비 우선 탐색과 깊이 우선 탐색이 어떤 거지 와 닿으시나요?

너비 우선은 매 단계에서 가능한 모든 경우의 수를 확인,
깊이 우선은 한 우물만 파고들며 끝을 볼 때까지 확인! 이라는 것만 이해하면 다 이해한 겁니다!!

깊이 우선 탐색, Depth First Search (DFS)

깊이 우선 탐색, DFS는 위에서 "한 우물만 깊게 파서 끝을 보는 탐색" 이라고 얘기했었죠.

그렇다면 위의 간단한 트리에서 DFS 를 이용한다면 어떤 순서로 탐색을 하게 될까요?

먼저 루트 노드 (시작점) 인 A 부터 시작해서, 그 자식인 B, C, D 를 확인할 것입니다. 그 중 하나를 골라 더 깊게 들어가겠죠. B 를 골라서 들어간다면, 또 그 다음 자식인 E 로 내려가고, 그 후에 I 까지 확인하니 끝을 만납니다. 이런 식으로 모든 노드들의 끝을 볼 때까지 계속 깊게 들어가면서 탐색할 겁니다.

정확한 순서는, A → B → E → I → J → C → F → D → G → H → K 가 됩니다. 그림으로 보면 다음과 같죠!

이 순서가 어떻게 나오는지 스택까지 같이 보면서 확인해 보겠습니다.

아래 그림의 다홍색 박스가 스택입니다. 차곡차곡 노드들을 쌓아 넣고, 다시 꺼낼 때는 맨 위에 있는 노드, 즉 방금 넣은 노드부터 꺼내야 하죠.

DFS에서는 한 단계에서 Pop 과 Expand 두 가지 일을 동시에 처리합니다.

Pop 은 스택의 맨 위 노드를 꺼내는 일을 말합니다. 그림에서는 / 를 이용해 노드를 지우는 것으로 표현합니다.
Expand 는 pop으로 노드를 지우면서 그 노드의 자식을 모두 스택에 넣는 일을 말합니다. 자식이 없다면 아무것도 넣지 않습니다.

따라서 위의 두 가지 일을 순서대로 처리하면 다음과 같이 13단계를 거쳐 모든 노드의 탐색을 할 수 있습니다.

그림을 손으로 직접 그리고 지워보면서 순서대로 따라가 보세요!

1) 루트 노드 (시작점) 인 A 를 스택에 넣습니다.

2) A 를 Pop 하면서 Expand 합니다. 즉, A 는 지우고 A 의 자식인 B, C, D 를 스택에 넣습니다.

3) 스택의 맨 위에 있는 B 를 Pop and Expand 합니다. 즉, B 는 지우고 B 의 자식인 E 를 스택에 넣습니다.

4) 스택의 맨 위에 있는 E 를 Pop and Expand 합니다. 즉, E 는 지우고 E 의 자식인 I, J 를 스택에 넣습니다.

5) 스택의 맨 위에 있는 I 를 Pop and Expand 합니다. 이 때, I 는 자식이 없으므로 (끝에 도달했으므로) 스택에 넣을 것이 없습니다.

6) 스택의 맨 위에 있는 J 를 Pop and Expand 합니다. 이 때, J 또한 자식이 없으므로 스택에 넣을 것이 없습니다.

7) 스택의 맨 위에 있는 C 를 Pop and Expand 합니다. 즉, C 는 지우고 C 의 자식인 F 를 스택에 넣습니다.

8) 스택의 맨 위에 있는 F 를 Pop and Expand 합니다. 이 때, F 는 자식이 없으므로 스택에 넣을 것이 없습니다.

9) 스택의 맨 위에 있는 D 를 Pop and Expand 합니다. 즉, D 는 지우고 D 의 자식인 H, K 를 스택에 넣습니다.

10) 스택의 맨 위에 있는 G 를 Pop and Expand 합니다. 이 때, G 는 자식이 없으므로 스택에 넣을 것이 없습니다.

11) 스택의 맨 위에 있는 H 를 Pop and Expand 합니다. 이 때, H 는 자식이 없으므로 스택에 넣을 것이 없습니다.

12) 스택의 맨 위에 있는 K 를 Pop and Expand 합니다. 이 때, K 는 자식이 없으므로 스택에 넣을 것이 없습니다.

13) 스택이 비었습니다. 이 말은 모든 노드를 탐색했다는 뜻이죠!

이렇게 간단한 트리에서의 DFS 탐색 과정을 모두 알아보았습니다.

그렇다면 조금 더 복잡한 트리에서 DFS 탐색 순서는 어떻게 될지 한 번 풀어볼까요? 조금 더 복잡할 뿐, 원리는 같습니다!

( 답을 보기 전에 한 번 탐색 경로를 찾아보세요! )

답은 A → B → F → C → G → K → L → O → P → Q → S → T → H →M→ D → I → E → J → N → R 입니다. 간단하죠?!

마지막으로, DFS 를 구현하는 파이썬 코드를 확인해 보겠습니다.

괜찮은가요? 위에서 쭉 봐왔던 과정을 그대로 코드로 옮긴 것인데, 주석을 지우면 꽤 간단할 겁니다..!

처음 노드를 stack에 넣으면서 시작하고,
while 문에 들어가면서 stack이 비었는지 확인합니다. 비어있다는 것은 모든 노드를 탐색했다는 뜻인데, 만약 찾고자 하는 TARGET 이 있는데 스택이 비었다면 "전부 찾아봤지만 TARGET 은 없었다"는 뜻이 되겠죠.
스택이 비어있지 않다면 맨 위에서 노드 하나를 pop 합니다.
방금 꺼낸 노드가 TARGET 인지 확인 해봐야겠죠! 일치한다면 원하는 타겟을 찾은 것입니다!
타겟이 아니라면 노드를 expand 해서 자식 노드들을 구하고,
그 자식 노드들을 stack 에 다시 차곡차곡 쌓습니다.
이렇게 target을 찾거나, 전부 탐색해서 stack이 빌 때까지 while 문을 반복하면 되겠습니다!

여기까지 DFS의 탐색 과정과 구현 코드까지 확인해 보았습니다. 다음은, DFS의 짝꿍인 BFS로 가시죠!

너비 우선 탐색, Breadth First Search (BFS)

너비 우선 탐색은 첫 번째 수에서 가능한 모든 것을 확인하고, 두 번째 수에서 가능한 모든 것을 확인하고, ... 이렇게 한 수 한 수 전부 확인하며 천천히 깊어지는 탐색이었습니다. 말로 하는 설명은 그만 하고, 바로 그림으로 확인해 보죠.

DFS 에서 사용했던 간단한 트리를 BFS 로 탐색하면 순서가 어떻게 달라질까요? 바로 다음 그림과 같습니다!

알파벳을 써 놓은 순서 그대로, A → B → C → D → E → F → G → H → I → J → K 가 되겠네요.

왜 이런 순서가 될까요?

말했듯이 BFS는 날개를 펼치듯 한 수에서 가능한 수를 다 그려보고, 그 다음 단계에서도 가능한 수를 다 확인하는 순서로 탐색하기 때문에 한 층을 내려가기 전에 그 층에 있는 모든 노드를 방문하기 때문입니다.

역시 BFS가 사용하는 자료구조 큐를 확인해 보면서 탐색 과정을 뜯어봅시다.

큐는 아래 그림에서 큐는 예시로 들었던 배드민턴 공을 담는 통처럼, 가로로 그려진 주황색의 열린 박스로 표현했고, 자료를 넣을 땐 오른쪽에서 넣고, 꺼낼 땐 왼쪽에서 꺼낼 것입니다.

BFS 또한 순서만 다를 뿐, Pop 과 Expand 과정을 똑같이 합니다. 다만, 스택의 pop 은 맨 뒤에서 꺼내지만 큐는 맨 앞에서 꺼내야 하기 때문에 용어가 조금 다릅니다. Pop 대신 Dequeue 라는 용어를 사용 하죠! (queue에 노드를 넣는 것은 Enqueue 라고 합니다. )

Dequeue 는 큐에서 맨 앞에 있는 노드를 꺼내는 일입니다. 그림에서 / 를 이용해 표현했습니다.
Expand 는 dequeue로 노드를 지우면서 그 노드의 자식을 모두 큐에 넣는 일을 말합니다. 역시 자식이 없다면 아무것도 넣지 않습니다.

BFS의 과정도 위의 두 가지를 반복하면서 처리하면 다음과 같은 순서로 탐색하게 됩니다.

큐는 가장 왼쪽에 있는 노드만 꺼내기 때문에 노드가 지워지는 위치가 모두 같네요!

역시 그림 순서대로의 과정은 다음과 같습니다.

루트 노드 (시작점) 인 A 를 큐에 넣습니다.
A 를 Dequeue 하면서 Expand 합니다. 즉, A 는 지우고 A 의 바로 다음 자식인 B, C, D를 큐의 오른쪽에 넣습니다.
큐의 맨 왼쪽에 있는 B 를 Dequeue and Expand 합니다. 즉, B 는 지우고 B 의 바로 다음 자식인 E 만 큐에 넣습니다.
큐의 맨 왼쪽에 있는 C 를 Dequeue and Expand 합니다. 즉, C 는 지우고 C 의 바로 다음 자식인 F 를 큐에 넣습니다.
큐의 맨 왼쪽에 있는 D 를 Dequeue and Expand 합니다. 즉, D 는 지우고 C 의 바로 다음 자식인 G, H 를 큐에 넣습니다.
큐의 맨 왼쪽에 있는 E 를 Dequeue and Expand 합니다. 즉, E 는 지우고 E 의 바로 다음 자식인 I, J 를 큐에 넣습니다.
큐의 맨 왼쪽에 있는 F 를 Dequeue and Expand 합니다. 이 때, F 는 자식이 없으므로 큐에 넣을 것이 없습니다.
큐의 맨 왼쪽에 있는 G 를 Dequeue and Expand 합니다. 이 때, G 는 자식이 없으므로 큐에 넣을 것이 없습니다.
큐의 맨 왼쪽에 있는 H 를 Dequeue and Expand 합니다. 즉, H 는 지우고 H 의 바로 다음 자식인 K 를 큐에 넣습니다.
큐의 맨 왼쪽에 있는 I 를 Dequeue and Expand 합니다. 이 때, I 는 자식이 없으므로 큐에 넣을 것이 없습니다.
큐의 맨 왼쪽에 있는 J 를 Dequeue and Expand 합니다. 이 때, J 는 자식이 없으므로 큐에 넣을 것이 없습니다.
큐의 맨 왼쪽에 있는 K 를 Dequeue and Expand 합니다. 이 때, K 는 자식이 없으므로 큐에 넣을 것이 없습니다.
큐가 비었습니다. 모든 노드를 탐색했다는 뜻이죠!