JAVA_코딩테스트 준비_탐색 알고리즘_(BFS/DFS)

BFS / DFS

그래프에서 탐색은 배열에서 나열된 요소들을 보는것과 달리 마치 무작위로 흩뿌려져 있는것들을 일일히 들여다 보는것과 비슷한 형태를 띈다.

그래서 특정한 값을 찾고 싶거나, 최단거리를 찾고싶거나 하면, 모든 정점들을 한번씩 방문해봐야 알 수 있다. 

우리가 길찾기 어플을 쓸때 최단거리를 알려주는것 처럼, 특정 정점을 거쳐 원하는 결과를 가져다 준다. 

 

BFS (너비 우선 탐색)

 

BFS 예시 (출처 : 코드스테이츠)

너비 우선탐색은 루트기준으로 가까운 정점부터 탐색하게 된다. 

마치 경로를 타고 한줄로 죽 가서 보는게 아니고 일일히 하나하나 옆으로 옮겨가면서 보는것과 비슷하다. 

위의 GIF는 미국으로 가는 목적지의 최단거리를 찾는 것인데, 경유횟수가 적은 경로가 가장 최단거리임을 알 수 있는 경우이다. 

주로 Queue를 이용하여 구현한다.

DFS (깊이 우선 탐색)

DFS 예시 (출처 : 코드스테이츠)

깊이 우선탐색은 경로를 따라 쭉 끝까지 모든 정점을 탐색하게 된다.

해당 그래프의 말단부까지 가서, 더 이상 진행 방향이 없으면 다시 이전의 분기가 가능한 정점으로 돌아와서 다시 경로를 따라 탐색을 진행하게된다. 

위의 GIF는 특정 비행기가 미국에 가는 경로를 가지고 있는지 탐색하는 예시이다.  

DFS는 한 정점에서 다음 경로로 넘어가기 전에 해당경로를 완전히 탐색할때 사용된다. 

그렇게 때문에 모든 경로를 탐색하지 않아도 도중에 목적으로 하는 결과값이 도출되면 작동을 중지하고 출력이 가능하다. 

 DFS는 주로 스택, 재귀함수로 구현한다.

하지만, BFS의 경우, 완전한 탐색을 하는 것이 아니기 때문에, 최악의 경우 모든 경로, 정점을 다 방문하고서야 원하는 결과값을 얻을수 있는 경우가 있다.
(기본적으로 DFS에 비해 많은 경로를 탐색해야 하는 경우가 많다.)

그렇기 때문에, 

• 그래프 규모가 작고, 깊이가 얕으면 -> BFS가 더 유리할 수 있다.
  
  
• 그래프 규모가 크고, 깊이가 크면 -> DFS가 더 유리할 수 있다. 

 

한짤요약

DFS, BFS 한짤요약

 간단히 말하면, 만약 모래사장에 반지 등의 물건을 잃어버렷다고 하자, 

여기서 모래사장의 깊이는 사실 정해져 있고,도구는 막대기다

DFS는 막대기를 모래사장의 바닥까지 푹푹 찔러보면서 반지를 찾는 것이고, 
(현제 정점에서 갈 수 있는 정점까지 쭉 들어가서 탐색)

BFS는 막대기를 모래사장의 표면부터 좌 우로 흔들면서 슥삭슥삭 파해치며 반지를 찾는 것이라고 생각하면 쉽다.
(현재 정점에 연결된 가까운 점들부터 탐색)

 

DFS, BFS 활용 문제 유형

코딩테스트에 자주 등장하는 녀석들이라서, 일단 어느정도 더 써보려고 한다.. 

나중에는 문제 예시 코딩문제도 풀어보면서 해설 해봐야 할듯...

일단 유형은 크게 3가지 

1. 그래프의 모든 정점을 방문하는 문제 : 단순히 모든 정점을 보고 싶은거면 DFS / BFS 둘다 상관없다. 구현에 자신있는거로 골라서 하자.(나는 재귀함수 싫어해서 최대한 재귀 안쓰는거로 할듯)
   
   
2. 경로의 특징을 저장해야 하는 문제 : 특정 경로에 장애물이 있거나, 조건이 필요한 문제는 DFS로 풀자. 
   경로의 변화, 특징을 저장할때는 DFS가 유리하고, 경로를 하나하나 보기때문에 더 정확할 수 있다. 
   또한, BFS는 경로의 특징을 가지지 못한다고 한다.
   
   
3. 최단거리를 구해야 하는 문제 : 깊이가 정해져 있지 않고, 무작위 깊이값을 가진 정점 중 하나가 정답일 것 같으면, BFS가 더 효과적이다
   깊이 우선 탐색(DFS)은 목표 경로로 도달 할때의 경우를 알 수 있지만, 자신이 처음에 발견한 값이 최단거리가 아닐 수 있다.(A 에서 B로 갈때 어디 들러서 갈수도 있고, 바로 갈수도 있다는 거다.)
   넓이 우선 탐색(BFS)은 가까운것부터 찾게 되므로 먼저 원하는 결과값 (A출발, B도착)이 최단거리이기 때문