1260 DFS와 BFS
문제
그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다.
입력
첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다.
출력
첫째 줄에 DFS를 수행한 결과를, 그 다음 줄에는 BFS를 수행한 결과를 출력한다. V부터 방문된 점을 순서대로 출력하면 된다.
문제 풀이
// 백준 1260번 DFS 와 BFS
const fs = require("fs");
const input = fs.readFileSync("input.txt").toString().trim().split("\n");
const nmv = input.shift().split(" ").map(Number);
let graph = Array.from(Array(nmv[0] + 1), () => new Array());
for (let i = 1; i <= nmv[1]; i++) {
let node = input.shift().split(" ").map(Number);
graph[node[0]].push(node[1]);
graph[node[1]].push(node[0]);
}
graph.map((el) => el.sort((a, b) => a - b));
let dfsAns = [];
let bfsAns = [];
const dfs = (graph, v, visited, ans) => {
// 현재 노드 방문 처리
visited[v] = true;
ans.push(v);
// 현재 노드와 인접한 다른 노드들을 재귀적으로 방문
for (i of graph[v]) {
// 방문한 적 없는 노드
if (!visited[i]) {
dfs(graph, i, visited, ans);
}
}
return ans;
};
const bfs = (graph, start, visited, ans) => {
let queue = [];
queue.push(start);
// 현재 노드 방문 처리
visited[start] = true;
// 큐가 빌 때까지 반복
while (queue.length != 0) {
// 큐에서 원소 뽑아서 출력 (선입선출)
let v = queue.shift();
ans.push(v);
// 아직 방문하지 않은 인접 원소들 큐에 삽입
for (i of graph[v]) {
if (!visited[i]) {
queue.push(i);
visited[i] = true;
}
}
}
return ans;
};
let visited = Array(9).fill(false);
let a = dfs(graph, nmv[2], visited, dfsAns);
visited.fill(false);
let b = bfs(graph, nmv[2], visited, bfsAns);
console.log(...a);
console.log(...b);
입력을 받아서 인접 리스트를 만들어서 정렬을 해야했다. 작은 번호부터 해야하니까 정렬 해주는 부분이 꼭 필요하다.
또한 원래 구현했던 DFS, BFS에서는 그때 그때 콘솔 출력을 하여 줄바꿈이 되어서 출력되었기 때문에 출력 방식을 맞춰주기 위해선 미리 담아두었다가 출력해야했다.
앞서 문제 풀 때 배열 원소 출력시 줄바꿈 없이 출력하려고 별 난리를 쳤었는데 그냥 spread 연산자 썼으면 되는 걸... js 처음 배웠을 땐 당연하게 spread 썼는데 초심을 잃어 까먹었었나😅
console.log('bang log');