[TIL] 알고리즘 - 깊이 우선탐색, 너비 우선 탐색

 

 

 

 

엄청난 무더위가 계속되고 있다. 장마는 벌써 끝났다는데 적당한 소나기 정도로 비 와서 한 번씩 땅을 식혀주면 어떨까 할 정도로 무더위가 계속되는 나날이다. 올해 초 어쩌다 주니어 개발자 오픈 채팅방을 들어간 뒤로 종종 정보를 얻고 있는데, NKLKB 라인에서 재직 중이신 분이 말씀하기를 그분은 면접 때 알고리즘 질문만 주구장창 받았다고 한다. 신입 포폴을 보는 것이 의미가 없어서 그런 게 아닐까? 하는 게 그분의 생각이었다. 아무튼 알고리즘에 대한 의지가 조금 더 불타올랐다.🔥

 

내가 처음 시작한 알고리즘 공부는 지금 생각해보면 맨땅에 헤딩 수준이었던 거 같다. 어떤 거를 공부하고 어떻게 공부해야 하는지 몰라서 그랬기도 했지만 독학으로 하려고 해서 그랬던 거 같다. 다짜고짜 백준부터 풀었는데 문제도 막히고 List 같은 기본도 제대로 알지 못했을 때 그 절망감이란.... 그 뒤로 책도 보고 인터넷 영상도 보고 문제도 풀고 강의도 풀며 지금까지도 공부하고 있다. 

 

중간중간 코딩 테스트로 여러 번 봤는데 항상 손도 못 댈 정도로 엄두가 안나는 쪽은 탐욕(Greedy) 알고리즘과 탐색이었다. 모르는 것도 이제 많이 줄긴 했지만 아직 멀었다. 오늘은 그래서 탐색에 대한 정리 글이다. 

 

---

 

보통 알고리즘과 자료구조는 병행해서 공부하는 경우가 많다. 나는 자료구조를 먼저 공부했는데 연결 리스트와 트리를 공부하면서 신기했던 게 배열이나 큐, 스택같이 자바에 내장되어있는 클래스들을 사용하는 것이 아니라 객체들을 직접 만들고 직접 그 관계들을 설정하는 것이 생소하면서 재밌었다. 물론 어렵기도 했다. 

 

알고리즘 문제에 출제되는 DFS나 BSF 들도 처음에는 어떻게 구현하는지 어떤 클래스를 사용하는지 궁금했는데 공부하고 보니 연결 리스트를 구현했을 때처럼 직접 객체들을 만들고 그 관계들을 이어주는 것이었다. 그래서 그 과정들을 Pseudo code(의사 코드)로 작성해보았다.

 

 

넓이 우선 탐색 - BFS

 

1 단계 

탐색할 자료는 HashMap으로 구현했다. key 값으로 각 노드에 해당하는 값을 넣었고 해당 노드들과 이어지는 노드들의 목록들을 List로 value에 순차적으로 넣었다. DFS나 BSF 자료를 시각화해놓은 그림을 보면 트리와 비슷하게 생겼다. 아무래도 브루트 포스 같은 알고리즘과 달리 시간 복잡도가 절반으로 줄어드는  O(logN) 형태가 탐색에 유리하기 때문이지 않을까 싶다. 그러므로 파라미터로 탐색할 자료와 시작점을 알려줘야 한다. 

 

2 단계 

 

만약 다음과 같은 자료를 넓이 우선 탐색해본다고 해보자. 다음과 같은 방향으로 탐색이 진행될 것이다.

 

탐색을 하려면 포인터에게 넘어가는 위치를 알려줘야 한다. 이 값을 알려주기 위해서 이미 탐색이 끝난 노드들의 목록을 담은 리스트와 앞으로 탐색을 해야 할 목록을 알려줄 큐를 선언한다.

큐로 선언하는 이유는 :  value 값으로 관계가 이어진 노드들을 순차적으로 넣었으므로 HashMap은 이런 식으로 들어가 있을 것이다. 

 

key : "7"   , value : [6, 10]

key : "6"   , value : [7, 5, 9]

key : "10" , value : [7, 12]

key : "5"   , value : [6, 4]

key : "9"   , value : [6]

key : "12" , value : [10]

key : "4"  ,  value : [5]

 

탐색을 한다면 처음 최상단 노드 7에서 그 value 값 6, 10 노드를

10번 노드까지 탐색이 끝난 다음 6번 노드의 value 값 5, 9번 노드를 

10번 노드의 value값 12번 노드를 탐색

그리고 마지막 5번 노드의 value 4번 노드를 탐색하는 식으로 진행된다.

 

즉 각 value 값의 0번 노드는 부모 노드, 그다음 값들은 자식 노드들이므로 선입선출(FIFO)의 특징을 가진 큐로 선언해서 0번 인덱스는 탐색이 끝난 목록에, 그다음 값들은 앞으로 탐색을 해야 할 목록들에 넣어주는 것이다. (처음 작성해본 의사 코드라 조금 어색할 수 있습니다 ㅠㅠ )

 

BFS ( HashMap, 최상단 노드){

    이미 방문한 노드 List
    아직 탐색하지 않은 노드 Queue
    
    아직 탐색하지 않은 노드에 최상단 노드 추가
    
    아직 탐색하지 않은 노드 Queue의 사이즈가 0보다 클 동안
    	현재 포인터가 있는 탐색하지 않은 노드의 0번째 인덱스를 제거
	
    만약 방문한 노드 리스트에 현재 포인터가 없다면
    	방문한 목록에 해당 포인터 추가
    	탐색하지 않은 노드 Queue에 해당 노드의 value 값 추가

}

 

 

깊이 우선 탐색 - DFS

 

 

깊이 우선 탐색은 단 두 군데 빼고는 전부 동일하다. DFS는 다음과 같은 방식으로 탐색한다.

최상단 노드부터 오르 쪽부터 가장 아래 노드에서 왼쪽으로 탐색해 나가기 때문에 탐색해야 할 노드들의 목록을 BFS와 반대로 구현해야 한다. 왜냐면 HashMap에 value를 넣어주는 부분은 동일하기 때문이다. 그러므로 앞으로 탐색해야 할 노드들의 목록만 선입 후출(FILO)의 성격을 가진 Stack으로 바꿔주고, 0번째 인덱스가 아닌 가장 마지막 인덱스를 제거해주면 된다.

 

 

---

 

 

모든 지식들이 그렇듯이 원리를 알기 전에는 어렵지만 알고 나면 쉽다. 나에게 탐색은 그런 존재인 것 같다. 앞으로 코딩 테스트에서 풀 수 있는 , 아니 최소한 시도라도 해볼 수 있는 문제가 한 문제 더 늘었다고 생각하기 뿌듯하다. 이제 많이 왔다!