[알고리즘] 2023.02.25 DFS와 BFS에 대한 고찰

⚫️ 잘못된 방향

요즘 BFS와 DFS 문제를 풀고 있다. 비교적 최근에 풀었던 문제중 '프로그래머스 타겟넘버'를 풀면서 풀이를 작성하고, 내가 고민해온 과정을 블로그에 남겼는데 이 글을 본 친구에게 연락이 왔다.

친구가 본인이 이 문제와 BFS.DFS에 대한 문제풀이 방식을 정리해준 Notion 페이지도 보내줬다. 운동하느라 카톡을 조금 늦게 확인했는데 친구가 이건 혼자 생각할게 아니라며 통화를 하며 알려준다고 했다. 일단,,, 나름 문제를 풀고 '잘풀었다!'하고 끝냈던 상황이었는데, 어떤 방향으로 잘못흘러가고있는지 궁금해서 얼른 씻고 친구에게 연락을햇다.

멋지다! 연진아

 

⚫️ 문제의 포스팅

https://didu-story.tistory.com/420

[프로그래머스] (Swift) 타겟넘버 (lv.2) (BFS, 시간초과에 대한 고찰)

이 문제를 풀면서, '시간복잡도'에 대한 고민을 조금 깊게 해봤다. 시간복잡도에 대해서 고민할때도 친구와 이야기를 나눴었고, 친구가 문제를 풀기 전, 시간복잡도를 어떻게 생각해야하는지 조언해주었다. 친구의 말로는, 내가 시간복잡도 해결은 했지만, 시간복잡도를 해결하고 나서 알고리즘이 달라졌는데 그 것을 전혀 언급해주지 않았고, 그리고 애초에 알고리즘을 떠올린 방식부터가 잘못됐다고 했다. 

위에 저 포스팅을 캡쳐해왔는데, 어떤 부분이 내가 개념이 잘못잡혀있을까?

위 캡쳐본에서 드래그 해둔 곳을 보면 내가 이렇게 써놨다. 결국, 이 문제는 '모든 경우를 탐색, 즉 완전탐색'을 해야하기 떄문에 BFS알고리즘을 채택했다고 한다. 그럼, BFS는 뭘까? 

https://github.com/HotCodeBreakers/CodingTest/discussions/25

[개념정리] DFS+BFS (혹시,,, 문제풀이 전에 이코테 책을 보시나요!?) · Discussion #25 · HotCodeBreakers/Codi

여기에 내가 아주 잘 정리해놨듯, queue를 사용하는 알고리즘이며, 최단경로를 찾을때 주로 사용하는 알고리즘, 그리고 인접한 노드를 모두 방문하는 알고리즘이다. 

⚫️ 완전탐색? BFS?

⚠️ 여기서 내가 착각한 것 같다. '인접한 노드를 모두 방문한다.'라는 것 때문에, 완전탐색을 하기 위해서는 BFS가 필요하구나? 싶었던 것이다. 하지만, 완전탐색을 하는 방식에는 여러가지 방법이 있다. 인터넷에 대충만 쳐봐도, 완전탐색을 하는 방식에는 

• 브루트포스 기법 (반복문과 조건문응로 모두 테스트)
• 순열
• 재귀 
• 비트마스크 (2진수 표현기법 사용)
• BFS
• DFS

이렇게나 많은 완전탐색 방법이 있다. BFS는 완전탐색을 할 수 있는 알고리즘중 하나일 뿐이지, 완전탐색 = BFS 알고리즘을 사용해야지! 하는 생각의 흐름은 알고리즘 문제를 풀 때 맞지 않다. 물론, 완전탐색을 위한 한가지의 방법중 하나가 BFS겠지! 

▪️ BFS로 완전탐색을 하기 위해서는, 아주 좋은 성능의 큐가 필요하다. O(1)짜리 큐..!

하지만 BFS로 완전탐색을 구현하는 것은 굉장히 좋은 성능의 큐가 있어야한다. 그 이유는,, BFS는 인접한 모든 노드를 탐색하기 위해서 queue를 사용한다. 이떄 연산을 할때마다 한 개씩 pop해주는 과정이 필요한데, 이부분에서 O(1)이 아니면, 시간복잡도는 매우매우 커지게 된다. 

▪️ 그럼, O(1)짜리 큐가 있으면 BFS를 이용해서 완전탐색을 시도해도 좋을까?

음,,, 뭐 주어지는 N의 개수가 너무 많지만 않으면 돌아는 갈 것이다. 근데 이것을 공간복잡도 측면에서 생각해봐야한다.

그 이유는,, BFS는 인접한 모든 노드를 탐색하기 위해서 queue를 사용한다. 결국, 한개의 노드를 보면서 다음 인접한 노드를 모두!!! queue에 넣어주게 되는데 그럼,,, 그래프가 커지면 커질 수록 queue에 들어있는 데이터의 갯수는,, 상상을 초월할 정도로 많아질 것이다. 

BFS 이렇게 동작한다. 양옆으로 넓게 움직이면서 모든 노드를 탐색할 수 있도록 동작하여 '너비 우선 탐색'이라는 이름이 붙었다. BFS는 주로 어떤 문제에서 사용한다고 했지? 바로 최단 거리 탐색이다. 그 이유를 큐가 동작하는 방식을 살펴보면서 다시 잡아보자.

• 제일 처음, 0이 큐에들어간다. queue = [0]
• 0과 인접한 노드인 두개의 노드가 큐에 다시 들어가겠지? 그리고 탐색을 마친 노드 0은 pop되어 빠진다. queue = [1, 2]
• 다음 으로 볼 node는 queue에 가장 먼저 들어가있는 1이다. 1과 인접한 노드를 모두 queue에 넣어주고, 탐색을 마친 1도 pop되어 빠진다. queue = [2, 3, 4] 
• 다음 pop되어 살펴볼 노드는2이다. 2와 인접한 노드도 모두 queue에 넣어주고 탐색을 마친 2는 pop된다. queue = [3, 4, 5, 6]
• 위와 같은 방식으로 3, 4, 5, 6을 모두 살펴본다. 3,4,5,6은 모두 인접한 노드가 없기 때문에 추가로 queue에 append되지 않고 queue가 점차 비워진다.

이렇게 큐는 동작한다. 2^20의 경우의 수라고 생각했을 때, 큐에는 최악의 경우 2^20개 , 즉 큐는 100만 개 이상의 데이터를 보관하고, 처리해주어야한다. 완전탐색을 BFS로 하는 방식은... 공간복잡도 측면에서도, 시간복잡도 측면에서도 결코 좋은 방법은 아닌 것이다.

🔖 그럼 왜 큐를 사용하는 BFS 를 최단경로를 찾을 때 사용할까?

보통, 최단경로를 찾을때는, cost가 존재한다. 위 그림을 봤을때, 순차적으로 모든 노드를 탐색하고, 원하는 노드에 도달했을때 탐색을 멈추고, 최소 cost가 되게 해주면된다. 즉, BFS는 끝까지 모두 탐색한다기 보단, 원하는 노드에 도달하면 멈춰주면 된다.

끝까지 다 탐색하고 최소 찾는건? 물론 된다. BFS도 완전탐색의 일종이라니까!????? 근데, BFS알고리즘을 완전탐색으로 이용하는것은 옳지 못한 방법이다. Swift언어로 예를들어보자.

Swift에는 효율이 좋은 큐가 제공되지 않는다. 즉, Array를 사용해서 이를 '큐처럼' 이용해야한다. removeFirst()라는 메서드를 사용해서! 하지만,, removeFirst()의 시간복잡도는 O(N)이다. 그리고 대부분의 BFS 내부에는 반복문이 등장하게 되는데, 안그래도 O(N)이상이 되는 알고리즘에 pop을 해주기 위한 시간 O(N)을 또 써버리는 것은... 매우 효율이 떨어지겠지?

 

⚫️ 보통 완전탐색을 할 때는 DFS를 사용한다!

▪️ DFS는 stack 구조를 사용한다??  콜스택을 생각해!!

DFS에 대한 이야기를 나누면서 또 다시 새로운 사실?을 깨우쳤다. 보통 DFS는 '스택 자료구조를 사용한다'라고 설명한다. stack 자료구조를 사용하는건 알겠다... 하지만 DFS가 동작하는 방식 자체가 Stack 구조라는거!에 집중해야한다. 

DFS는 보통 재귀 활용하여 구현을 많이 하는데, 재귀라는 것 자체가 바로 함수의 콜스택에 함수가 쌓여나가는 과정이니까 stack 동작방식으로 동작하는 것이다. 호호호,,, 콜스택까지는 생각하지 못했는데, 어쨌든 stack 자료구조를 사용한다보다는, 콜스택에 함수가 쌓인다고 이해하는게 dfs를 이해는 더 빠른 방법일 것 같다. (그리고 보통 dfs코드는 재귀를 계속해서 불러서 결국 해답을 찾아내는 방식을 사용하지, bfs가 큐에 직접 데이터를 append 하는것처럼 dfs는 stack을 따로 만들고 거기에 append하면서 코드를 구현하진 않는다.)

▪️ DFS를 완전탐색할때 주로 사용한다?

💬 stack을 사용하는 이유, 동작방식을 살펴보면 답이 나온다.

DFS는 이렇게 움직인다. 그림을 봐도 딱 보인다시피, '완전히 끝까지!! 내려갔다가 다시 올라오고, 다시 올라오고 이런 방식으로 동작한다. 함수 콜스택에 어떻게 쌓이는지 살펴보면,

• 0 함수호출 
• 1 함수호출
• 3 함수호출
• 다음 없으니까 3에서 return 
• 올라가서 다음 남으 논드 4 함수호출
• 4 return
• 올라가서 1 return 
• 남은노드 2 함수호출,,,

이런식으로 콜스택에 쌓이게 된다. 함수가 호출되고 return 되는 과정을 보면, stack 자료구조와 동일하게 움직인다. (LIFO)

💬 그럼 왜 완전탐색할때 주로 BFS보다는 DFS를 채택할까?

func dfs(_ start: Int) {
    visited[start] = true
    print(start, terminator: " ")
    for i in 1..<n+1 {
        if visited[i] == false && matrix[start][i] == 1 {
            dfs(i)
        }
    }
}

일단, 재귀를 활용하기 때문에 DFS자체의 시간복잡도는 그리 작지 않다. 하지만, 공간복잡도의 측면에서도 살펴보자.

• 위와 동일하게 2^20의 경우의 수가 존재한다고 치자.
• dfs는 deep 하게 내려가기 때문에, 콜스택에 함수가 최대,,, 20개 정도 쌓일 것이다.
• 차례대로 20개를 return 해오고, 다시 내려가고, 다시 return 하고 이런 과정을 반복하겠지? 

이렇듯, 공간복잡도 측면에서 봣을 떄 BFS보다는 DFS가 더 완전탐색을 할 떄 적절하다.

 

⚫️ 문제의 포스팅으로 다시 돌아가자

https://didu-story.tistory.com/420

이 포스팅에서 적어놓은 일부분을 캡쳐해왔다. 여기서 '배열을 큐처럼' 사용해서 시간초과가 났다고 설명했고, 이를 stack 형식으로 바꾸니가 통과가 되었다고 적어놨다. 맞는말이다! 통과는 했으니까.

근데 여기서 단지 시간복잡도만 문제였을까? 아니다. 나는 애초에, BFS와 DFS의 개념혼동해서 생각했고, DFS로 구현해야하는 문제를 BFS로 구현했기 때문에 시간초과가 난 것이다. 이 개념을 바로잡아야했고,,, 이 개념을 바로잡기 위해서 친구가 긴 시간동안 조언을 해준 것이다.... 

결국 두번째 정답코드를 살펴보면, 재귀를 사용하진 않았지만, dfs 방식으로 돌아간다. (stack 자료구조를 사용한 DFS)
나는 이게 BFS로 풀었다고 믿고 풀었지만, 사실상 아니었단 것이다!!!!!! 

▪️ 내가 이 문제에 왜 잘못접근한 것인지 정리해보자

1. 완전탐색 -> 아, BFS로 풀어야지! 하는 생각의 흐름이 잘못됐다. 완전탐색으로 푸는 방식중에 하나일 뿐이지, 적합한 방식은 아니다.
2. '코드의 모양'이 BFS라서 BFS라고 믿고 풀었지만, 코드를 뜯어보고 동작하는 방식을 뜯어보니, 나는 BFS라고 치고 DFS코드를 구현하고 있었다. 'stack' 자료구조를 사용한 DFS로 결국 구현한 것이다. 여기서 내가 얼마나 개념을 혼동해서 사용하고 있고, 알고리즘의 개념을 제대로 인지하지 않은 채로 코드를 짜고있음을 파악했다.

🤔 잡담타임

어제 친구와 이 이야기에 대해서 2시간정도 대화를 나눈 것 같다. + 이것저것 내 취업고민과,, 다른 근황토크까지 곁들였지만
어쨌든, 이렇게 잘못된 부분에 대해서 친구가 말해주고, 바로잡아줘서 너무 고마웠다. 전공을 살리지 않은 외딴섬에 친구가 있어서 참말로 다행이었달까 ^___^

요즘들어 알고리즘에 대해서 더 깊게 고민하는 습관이 생긴것같다. bfs, dfs아 그렇구나, 에서 끝나는게 아니라, 왜 큐를 사용하고 왜 스택을 사용하지? 그럼 이거 시간복잡도는 어떻게되지? 공간복잡도도 생각해야하는구나? 그럼, 조건은 어떻게되지? 등등...

친구가 정리해둔 노션을 보니까, 친구가 얼마나 많이 고민을 하고 본인만의 정답을 찾아갔는지.. 눈에 보였고 너무 대단해보였다. 그리고, 시간복잡도에 대한 중요성도 다시 한번 언급해줬는데, 백준에서 실버1 이상, 골드까지 문제를 풀기 위해서는 내가 필수적으로 고민해봐야하는 문제들인것 같다.

문제를 풀기 전, 항상 조건을 먼저 생각하고, 최악의 경우 어떠한 시간복잡도를 가지는지 '추측'이라도 하고 문제를 푸는 습관을 길러야겠다. 결국 그래야만, 킬러문제를 맞출 수 있을 것 같다. 지금까지 시간복잡도의 중요성을 몰랐던 이유는, 바로 실버 그 언저리의 문제들을 푸느라 그랬던 것 같다. 그냥,, 냅다 코드로 갈겨쓰고 구현만 하면 돌아가는 문제들이 대부분이었다. 아 어쨌뜬,, 지금 이 글도 되게 횡설수설하게 정리했는데 그냥 내가 머릿속에 떠오르고, 기억하고싶었기 때문에 회고처럼 작성했다. 앞으로 나의 고민이 담긴 많은 글을 포스팅해서 더 많은 사람들과 개발토크를 진행해보고 싶다. 화이팅🍀

아 그리고 친구가 DFS BFS도 모르는데 프로젝트는 왜하냐고 해서 ㅋㅋㅋㅋㅋㅋㅋㅋㅋ 머리한대 맞은 것 같았다. 맞다 기초부터 다잡아야지!!!! 앞으로 문제를 푸는거에서 그치지 않고, 알고리즘 공부에 더 힘을 쏟아볼 예정이다.