DFS와 BFS를 파이썬으로만 풀어봤지, js로 바꾼 이후에 풀어본 적이 없다 !
저번에 풀었던 지식으로 대충 구현하면 되겠지라 생각하고 입문했는데, Queue가 없다는 소식에 두둥 ..
그래서 정리하면서 이해해보려 한다!
BFS
Queue가 없는 이상 BFS를 풀 수 있는 방법은 총 세 가지가 있었다. (내가 생각했을 때)
- Class를 사용해서 직접 Queue를 구현한다.
- 배열을 사용하여 푸는데, Queue를 앞에서 빼내는 것은 shift를 사용한다.
- 배열을 사용하여 푸는데, 인덱스를 하나 늘리면서 진행하여 '빠진 척' 진행한다.
1번은 매 코테때마다 생각하면서 구현하는 게 힘들다고 판단.
2번은 시간초과 날 가능성이 너무 많다.
따라서 3번으로 컨벤션을 세우면서 풀어나갈 것이다 :D
BFS 컨벤션
visited는 중복이 되지 않으니 집합으로 만든다.
queue로 사용할 배열도 선언.
빠진 척 진행할 변수는 front 변수를 사용한다.
일반적인 bfs
- 큐가 비었을 때 반복문을 그만둔다.
- 비지 않았으면 큐에서 제일 첫 번째 숫자를 빼낸다.
- 첫 번째 숫자의 이웃노드를 확인
- 이웃 노드가 방문되지 않았으면 visited에 추가하고, queue에다가 추가한다.
-> 반복
내가 구현할 bfs
- 큐가 비었을 때 반복문을 그만둔다.
-> front를 하나씩 늘리면서 진행할 건데 front가 queue의 제일 마지막에 갔을 때, 즉 queue가 비었을 때 그만둔다. - 비지 않았으면 큐에서 제일 첫 번째 숫자를 빼낸다.
-> front가 첫 번째를 나타내는 숫자이므로 front를 인덱스로 사용하여 queue[front]와 같이 빼낸다.
-> front 앞의 인덱스들은 모두 삭제되었다고 봐도 무방!!
-> 빼내고 front는 +1을 해줘야하므로 queue[front++]로 사용한다. - 첫 번째 숫자의 이웃 노드를 확인
-> graph에 이웃 노드가 들어있으므로 graph에다가 현재 노드를 넣어 neighbor를 꺼낸다. - 이웃 노드가 방문되지 않았으면 visited에 추가하고, queue에다가 추가한다.
bfs 컨벤션 코드
function bfs(graph, startNode) {
const visited = new Set();
const queue = [];
let front = 0;
queue.push(startNode);
visited.add(startNode);
// 큐가 비어있지 않는 동안
while (front < queue.length) {
const currentNode = queue[front++];
console.log(currentNode); // 현재 노드를 방문하거나 다른 작업 수행
const neighbors = graph[currentNode] || []; // 해당 노드의 이웃 노드들
for (const neighbor of neighbors) {
if (!visited.has(neighbor)) {
visited.add(neighbor);
queue.push(neighbor);
}
}
}
}
const graph = {
1: [3, 6],
3: [1, 5],
4: [6],
5: [3, 6],
6: [1, 4, 5],
};
bfs(graph, 1);DFS
DFS 컨벤션
- 시작 정점을 스택에 삽입한다.
- 스택에서 하나의 정점을 꺼낸다.
- 스택에서 꺼낸 정점이 아직 방문하지 않은 정점이라면, 방문 표시 후 이웃 정점들을 스택에 삽입한다.
- 스택에 담긴 정점이 없을 때까지 2-3번 과정을 반복한다.
DFS 컨벤션 코드
function dfs(graph, startNode) {
const visited = new Set();
const stack = [];
stack.push(startNode);
visited.add(startNode);
while (stack.length > 0) {
const currentNode = stack.pop();
console.log(currentNode);
const neighbors = graph[currentNode] || [];
for (const neighbor of neighbors) {
if (!visited.has(neighbor)) {
visited.add(neighbor);
stack.push(neighbor);
}
}
}
}
const graph = {
1: [2, 3],
2: [1, 4, 5],
3: [1],
4: [2],
5: [2],
};
dfs(graph, 1);
번외
인접리스트를 2차원 배열로 만들기
const input = fs
.readFileSync(filePath)
.toString()
.trim()
.split('\n')
.slice(1)
.map((value) => value.split(' ').map(Number));
Hello Velog