제목이 곧 내용입니다
차례
0. 시작하며
1. DFS와 BFS 가 먼데?
2. 그래서 이걸 언제 사용하는데?
3. 그래서 이걸 어떻게 사용하는데?
4. 마치며
0. 시작하며
이 글의 목적은 BFS와 DFS 가 뭔지 1도 모르는 사람에게 아주 아주 기초 사전 지식만 있으면 이해할 수 있도록 쓰려고 노력했다. 단순히 이해를 넘어, 이거 그래서 개발생활에 어떤 문제에서 쓸 수 있는지를 코테를 통해 설명하고자 한다.
완벽하게 이해할 필요 없이 '오, 그렇군?' 정도만 생각하고 넘어갈 수 있어도 좋을 것 같다. 이거 하나는 내가 확신한다.
나도 이해한 BFS와 DFS, 너도 이해할 수 있어!!
1. DFS 와 BFS 가 뭔데?
DFS(Depth-First Search)와 BFS(Breadth-First Search)는 그래프 탐색 알고리즘이다.
그래프는 이런 녀석이다.
0은 1과, 3과 4와 이어져 있고,
1은 0과 2와 이어져 있고,
3은 0과 2와 이어져 있고,
4는 0과 이어져 있고,
5는 4워 이어져 있다.
이걸 JS로 표현하면 다음과 같다.
const graph = [[1, 3, 4], [0, 2], [1, 3], [0, 2], [0, 5], [4]]; // 알아보기 어렵다
DFS와 BFS는 이렇게 생긴 그래프를 탐색하는 방법이다. 아래 그림처럼 움직인다고 보면 된다.
DFS는 Deep 하게 탐색하는 녀석이라 쭉쭉 아래부터 간다.
BFS는 Breadth(너비)로 탐색하는 녀석이라 같은 정점을 바라보는 녀석부터 찾는 게 특징이다.
2. 그래서 이걸 언제 사용하는데?
| DFS | BFS | |
| 탐색 방식 | 깊이 우선(깊게 탐색 후 백트래킹) | 너비 우선(가까운 노드부터 탐색) |
| 최단 경로 탐색 | ❌ | ✅ |
| 시간 복잡도 | O(V + E) (V: 노드 수, E: 간선 숫자) | O(V + E) (V: 노드 수, E: 간선 숫자) |
| 사용 예시 | 백트래킹, 체스 | 최단 거리 문제, 네트워크 탐색 |
DFS는 각 정점에 숫자가 적혀있고 a부터 b까지 가는 경로를 구하는데 경로에 같은 숫자가 있으면 안 된다는 문제 등, 각각의 경로마다 조건을 저장해야 할 때 쓰기에 알맞다. 표에 예시에 나온 백트래킹이란 경우의 수를 탐색하면서, 불가능한 경우를 제외(Pruning)하는 탐색 기법인데, BFS에서는 경로마다 특징을 가지지 못해, DFS를 사용하는 게 유리하다.
BFS는 하나의 정점을 바라보는 녀석부터 탐색하기 때문에, 가장 가까운 녀석 찾거나 할 때 유리하다.
3. 그래서 이걸 어떻게 사용하는데?
먼저 기본적인 BFS와 DFS의 js 코드를 여기서 긁어왔다.
(내 글이 이해가 안 가면 저 블로그를 보세요, 저기가 더 잘 설명한 듯)
DFS 구현 함수
// graph 자료구조와 startNode를 입력
const DFS = (graph, startNode) => {
const visited = []; // 탐색을 마친 노드들
let needVisit = []; // 탐색해야할 노드들
needVisit.push(startNode); // 노드 탐색 시작
while (needVisit.length !== 0) { // 탐색해야할 노드가 남아있다면
const node = needVisit.shift(); // queue이기 때문에 선입선출, shift()를 사용한다.
if (!visited.includes(node)) { // 해당 노드가 탐색된 적 없다면
visited.push(node);
needVisit = [...graph[node], ...needVisit];
}
}
return visited;
};BFS 구현 함수
// graph 자료구조와 startNode를 입력
const BFS = (graph, startNode) => {
let visited = []; // 탐색을 마친 노드들
let needVisit = []; // 탐색해야할 노드들
needVisit.push(startNode); // 노드 탐색 시작
while (needVisit.length !== 0) { // 탐색해야할 노드가 남아있다면
const node = needVisit.shift(); // 가장 오래 남아있던 정점을 뽑아냄.
if (!visited.includes(node)) { // 해당 노드 방문이 처음이라면,
visited.push(node);
needVisit = [...needVisit, ...graph[node]];
}
}
return visited;
};
그럼 이제 문제를 통해 BFS와 DFS를 활용해 보자.
https://school.programmers.co.kr/learn/courses/30/lessons/43163?language=javascript
프로그래머스
SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프
programmers.co.kr
문제 정의는 이렇다.
두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다.
1. 한 번에 한 개의 알파벳만 바꿀 수 있습니다.
2. words에 있는 단어로만 변환할 수 있습니다.
예를 들어 begin이 "hit", target가 "cog", words가 ["hot", "dot", "dog", "lot", "log", "cog"]라면 "hit" -> "hot" -> "dot" -> "dog" -> "cog"와 같이 4단계를 거쳐 변환할 수 있습니다.
두 개의 단어 begin, target과 단어의 집합 words가 매개변수로 주어질 때, 최소 몇 단계의 과정을 거쳐 begin을 target으로 변환할 수 있는지 return 하도록 solution 함수를 작성해 주세요.
제한사항
- 각 단어는 알파벳 소문자로만 이루어져 있습니다.
- 각 단어의 길이는 3 이상 10 이하이며 모든 단어의 길이는 같습니다.
- words에는 3개 이상 50개 이하의 단어가 있으며 중복되는 단어는 없습니다.
- begin과 target은 같지 않습니다.
- 변환할 수 없는 경우에는 0을 return 합니다.
입출력 예
| begin | target | words | return |
| "hit" | "cog" | ["hot", "dot", "dog", "lot", "log", "cog"] | 4 |
| "hit" | "cog" | ["hot", "dot", "dog", "lot", "log"] | 0 |
입출력 예 설명
예제 #1
문제에 나온 예와 같습니다.
예제 #2
target인 "cog"는 words 안에 없기 때문에 변환할 수 없습니다.
'어라? 이게 왜 BFS / DFS로 푸는 거지?' 싶었다. 어떻게 그래프를 그려야 하는지도 모를 거다. 나도 잘 모르겠다.
일단 그래프부터 그려보자! 문제에서 주어진 words 배열의 각 원소 사이에는 연결 관계가 없지만, 다른 노드에 방문하는 조건이 있다. 바로 '한 글자'가 다를 때 방문한다는 것이다.
어라? 그러면, 'hit'라는 단어와 words 들 사이를 연결할 수 있을 것 같다. 한 글자가 다른 것들은 사실 다음 방문지라고 생각해도 되니까!
어라? 그리고 이거, '가장 짧은 변환 과정'이네? 그렇다면 최단 거리를 찾는 문제니 BFS를 사용해야겠다!!
정정...ㅠ
*최단 거리를 찾을 때 BFS 가 맞으나, 다시 생각해 보니 위 문제 같은 경우, 어차피 정점이 정해져 있고 한 단어씩 바꾸는 거라 '최단 거리' 워딩과 다르게 DFS를 사용해도 괜찮았을 문제였을 것 같다. BFS와 DFS를 설명하기에 애매한 코태를 선정한 것 같다ㅠ 읽는 여러분은 글자에 현혹되어 저처럼 실수하지 마세요ㅠㅠ
오호라! 그렇다면 BFS 코드에 그대로 집어넣으면 되겠다!
function solution(begin, target, words) {
const visited = { [begin] : 0 }; // init 값 푸시를 그냥 바로 했다.
const needVisit = [begin]; // 얘가 queue 다
while(needVisit.length) {
const node = needVisit.shift(); // 가장 오래된 녀석 꺼냄
if(node === target) break;
for(const word of words) {
if(!visited[word]) { // 해당 노드 방문이 처음이라면
visited[word] = visited[node] + 1; // 몇 번째인지 순서를 적어두자!
needVisit.push(word);
}
}
}
return visited[target] ? visited[target] : 0; // 없으면 0 return 해야 하니까!
}
앗! 그런데, 이동할 수 있는 조건이 제한되었었잖아? 글자 중 하나만 같을 경우 호출하도록 조건이 추가되어야겠다!
// 글자중 하나만 같을 경우 호출 (왜냐면 이게 사실상 연결된 노드니까!)
const canTransfer = (str1, str2) => {
let count = 0;
for (let i = 0; i < str1.length; i++) {
if (str1[i] !== str2[i]) count++;
if (count > 1) return false;
}
return count === 1;
};
그럼 이렇게 하면 되겠다!
최종 코드
function solution(begin, target, words) {
const visited = { [begin] : 0 };
const needVisit = [begin];
while(needVisit.length) {
const node = needVisit.shift();
if(node === target) break;
for(const word of words) {
if(canTransfer(word, node) && !visited[word]) { // 방문되는 녀석 중 해당 노드 방문이 처음이라면
visited[word] = visited[node] + 1;
needVisit.push(word);
}
}
}
return visited[target] ? visited[target] : 0;
}
// 글자중 하나만 같을 경우 호출 (왜냐면 이게 사실상 연결된 노드니까!)
const canTransfer = (str1, str2) => {
let count = 0;
for (let i = 0; i < str1.length; i++) {
if (str1[i] !== str2[i]) count++;
if (count > 1) return false;
}
return count === 1;
};
방문 조건을 추가해 주면 끝! 이렇게 BFS와 DFS를 실제 코태에 적용해 봤다. 나처럼 '이 녀석 언제 써먹지?' 싶은 사람들에게 도움이 되었으면 좋겠다.
4. 마치며
DFS와 BFS의 개념만 알고 있을 때는 그걸 어따 쓰는지 몰랐지만, 코테를 풀면서 고민해 가며 알아가는 과정이 보람찼다.
하지만 다 풀고 알았는데, 이건 BFS와 DFS 간의 차이를 설명하기에 좋은 예제가 아니었던 것 같은데 시간관계상 냅다 제출했다. 이 부분은,, 여유롭게 글을 시작해 완성도를 높이는 것으로 해야겠다.
그리고 사실 내가 푼 거랑 다른 좋은 예제를 많이 참고했는데, 그 과정 중 내 경험을 보여주는 거와 모두가 이해하기 좋은 글을 쓰는 거 사이 밸런스를 살짝 고민했다.
사실 제일 좋은 건 모두가 이해하기 좋게 만든 내 경험을 보여주는 거란 거 알고 있다.
언젠가 내가 스스로 그런 수준이 되길 바란다. Try Try~
도움 받은 것들
쉽게 설명한 블로그
https://velog.io/@lucky-korma/DFS-BFS%EC%9D%98-%EC%84%A4%EB%AA%85-%EC%B0%A8%EC%9D%B4%EC%A0%90
DFS, BFS의 설명, 차이점
그래프란, 정점(node)과 그 정점을 연결하는 간선(edge)으로 이루어진 자료구조의 일종을 말하며,그래프를 탐색한다는 것은 하나의 정점으로부터 시작하여 차례대로 모든 정점들을 한 번씩 방문하
velog.io
이쁘게 설명한 블로그
Home
기록하는 프론트엔드 개발자
chamdom.blog
'알고리즘' 카테고리의 다른 글
| [자료구조] 이진탐색 (0) | 2023.06.05 |
|---|