DFS와 BFS가 햇갈려서 쓴 글

1. 정의

우선 DFS와 BFS의 정의부터 간략하게 다시 알고 가도록 하자.

DFS

깊이 우선 탐색이라는 이름에 맞게 탐색할 노드를 깊이를 우선으로 탐색하는 알고리즘이다.

DFS의 구현은 Stack 또는 재귀적인 특징을 이용해 구현한다.

 

한 노드의 하위 노드를 우직하게 계속 타고 가며 탐색한다

 

BFS

너비 우선 탐색은 넓게 바로 아래 하위 노드를 모두 넓게 탐색한 뒤 그 아래의 노드들을 탐색하는 알고리즘이다.

큐를 이용해 탐색을 관리한다.

넓게 탐색하는 것을 우선적으로 동작하는 모습이다.

 

 

이 자료를 보면 DFS와 BFS의 동작의 차이점을 볼 수 있다.

 

2. 구분 방법

그렇다면, 실제 코테나 문제를 해결할 때 무엇을 언제 사용해야하나?

우선 그 문제를 분석해봐야한다.

 

그래프 탐색에서 모든 정점을 방문하는가?

DFS와 BFS 둘 다 가능하다.

 

경로의 특징을 저장 혹은 조합, 순열을 구해야 하는 문제인가?

고로타면 DFS를 이용하는게 유리하다.

 

최단 경로, 최단 거리를 구해야 하는 문제인가?

그렇다면 BFS를 이용하는게 유리하다.

 

 

 

예시 문제

그렇다면 예시 문제를 보도록 할까?

 

내가 뽑은 DFS 예시 문제

• https://58cjdcns99.tistory.com/entry/JS-2Level-%EC%99%84%EC%A0%84%ED%83%90%EC%83%89-%EC%9A%94%EA%B2%A9-%EC%8B%9C%EC%8A%A4%ED%85%9C

[JS] 2Level / 완전탐색 / 요격 시스템

• https://58cjdcns99.tistory.com/entry/JS-%ED%9E%8C%ED%8A%B8-2Level-SummerWinter-Coding2018-%EC%8A%A4%ED%82%AC%ED%8A%B8%EB%A6%AC-1

[JS] 힌트 2Level / 완전탐색 / 피로도

• https://58cjdcns99.tistory.com/entry/1Level-SummerWinter-Coding2018-%EC%86%8C%EC%88%98-%EB%A7%8C%EB%93%A4%EA%B8%B0

1Level / Summer/Winter Coding(~2018) / 소수 만들기

• https://58cjdcns99.tistory.com/entry/1Level-%EC%97%B0%EC%8A%B5%EB%AC%B8%EC%A0%9C-%EC%82%BC%EC%B4%9D%EC%82%AC

1Level / 연습문제 / 삼총사

• https://58cjdcns99.tistory.com/entry/%EA%B9%8A%EC%9D%B4-%EC%9A%B0%EC%84%A0-%ED%83%90%EC%83%89-3-%EC%97%AC%ED%96%89%EA%B2%BD%EB%A1%9C-JS-%EB%B6%80%EC%A1%B1

깊이 우선 탐색 / 3 / 여행경로 (JS) 부족...

• https://58cjdcns99.tistory.com/entry/%EA%B9%8A%EC%9D%B4-%EB%84%88%EB%B9%84-%EC%9A%B0%EC%84%A0-%ED%83%90%EC%83%89-1-%ED%83%80%EA%B2%9F-%EB%84%98%EB%B2%84

깊이-너비 우선 탐색 / 2 / 타겟 넘버 (JS) dfs

• https://school.programmers.co.kr/learn/courses/30/lessons/12978

프로그래머스

 

위의 문제 모두 조합 또는 순열, 경로의 특징을 이용한 문제들이다.

 

내가 뽑은 BFS 문제들

• https://58cjdcns99.tistory.com/entry/%EA%B9%8A%EC%9D%B4-%EB%84%88%EB%B9%84-%EC%9A%B0%EC%84%A0-%ED%83%90%EC%83%89-3-%EB%8B%A8%EC%96%B4-%EB%B3%80%ED%99%98

깊이-너비 우선 탐색 / 3 / 단어 변환 (JS) bfs

• https://58cjdcns99.tistory.com/entry/JS-2Level-%EA%B9%8A%EC%9D%B4%EB%84%88%EB%B9%84-%EC%9A%B0%EC%84%A0-%ED%83%90%EC%83%89DFSBFS-%EA%B2%8C%EC%9E%84-%EB%A7%B5-%EC%B5%9C%EB%8B%A8%EA%B1%B0%EB%A6%AC

[JS] 2Level / 깊이/너비 우선 탐색(DFS/BFS) / 게임 맵 최단거리

• https://58cjdcns99.tistory.com/entry/Nodejs-2178%EB%B2%88-%EB%AF%B8%EB%A1%9C-%ED%83%90%EC%83%89

[Nodejs] 2178번 미로 탐색

• https://58cjdcns99.tistory.com/entry/JS-2Level-%EC%97%B0%EC%8A%B5%EB%AC%B8%EC%A0%9C-%EB%AC%B4%EC%9D%B8%EB%8F%84-%EC%97%AC%ED%96%89

[JS] 2Level / 연습문제 / 무인도 여행

위의 문제들에서 볼 수 있듯이 bfs는 최단기간 혹은 최단경로를 구할 때 유용한 알고리즘이다.