7번의 시도 끝에 성공...😵
BFS와 DFS 모두 모든 정점을 방문한다는 것은 동일하지만, 각각 방문하는 경로가 다르다.
DFS는 현재 정점과 연결된 정점 중 한 정점에만 방문할 수 있다.
단, 방문할 수 있는 정점들의 모든 경우의 수를 방문해봐야 한다.
(1과 연결된 정점이 2, 3이라면 2를 방문하는 경우와 3을 방문하는 경우를 모두 수행해야 한다.)
방문했던 지점을 다시 거치는 것도 가능하다! (방문으로 따지지는 않으므로 결과를 담는 배열에 추가하지는 않는다.)
BFS는 현재 정점과 연결된 정점을 동시에 모두 방문할 수 있다.
방문한 정점을 queue에 담아놓고, queue에 담긴 정점들을 앞에서부터 하나씩 꺼내서 해당 정점과 연결된 모든 정점을 (동시에) 방문한다.
queue에 담긴 정점을 모두 방문하면 끝!
방문 여부를 담을 check 배열을 활용하면 중복을 피할 수 있다.
해당 정점과 연결된 정점이 하나도 없는 경우에 대한 처리를 해주지 않으면, 참조 에러가 발생한다!
연결된 정점이 있는 경우만 배열 순회를 수행하도록 if문을 추가해서 해결했다✌🏻
위 사례를 확인할 수 있는 반례
input
5 4 1
2 3
3 4
4 5
5 2
output
1
1
const fs = require("fs");
const input = fs.readFileSync("/dev/stdin").toString().trim().split("\n");
// 시작할 정점
const start = Number(input[0].split(" ")[2]);
// 각 정점과 연결된 정점을 담은 배열
const temp = [];
for (let i = 1; i < input.length; i++) {
const left = Number(input[i].split(" ")[0]);
const right = Number(input[i].split(" ")[1]);
if (temp[left]) temp[left] = [...temp[left], right];
else temp[left] = [right];
if (temp[right]) temp[right] = [...temp[right], left];
else temp[right] = [left];
}
// 오름차순으로 정렬
const nodeList = temp.map((el) => el.sort((a, b) => a - b));
// DFS
const dfsResult = [];
const dfs = (vertex) => {
if (dfsResult.includes(vertex)) return;
dfsResult.push(vertex);
// 정점과 연결된 정점이 있는 경우만 수행
if (nodeList[vertex])
nodeList[vertex].forEach((el) => {
dfs(el);
});
};
dfs(start);
// BFS
const bfsResult = [];
const check = [];
const queue = [start];
const bfs = () => {
const vertex = queue.shift();
if (check[vertex]) return;
if (bfsResult.includes(vertex)) return;
check[vertex] = true;
bfsResult.push(vertex);
if (nodeList[vertex])
nodeList[vertex].forEach((el) => {
queue.push(el);
});
};
while (queue.length) {
bfs(start);
}
console.log(...dfsResult);
console.log(...bfsResult);