반응형
문제
https://www.acmicpc.net/problem/1260
1260번: DFS와 BFS
첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사
www.acmicpc.net
풀이
const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "./input.txt";
let [nums, ...arr] = fs.readFileSync(filePath).toString().trim().split("\n");
const [n, m, v] = nums.split(" ").map(Number);
const pairs = arr.map((pair) => pair.split(" ").map(Number));
let graph = Array.from({ length: n + 1 }, () => []);
let dfsPath = [];
let bfsPath = [];
// 인접 리스트
for (let [s, e] of pairs) {
graph[s].push(e);
graph[e].push(s);
}
graph = graph.map((v) => v.sort((a, b) => a - b));
function getDFSPath(v) {
let ch = Array.from({ length: n + 1 }, () => 0);
ch[v] = 1;
dfsPath.push(v);
function DFS(v) {
for (let i = 0; i < graph[v].length; i++) {
const nv = graph[v][i];
if (ch[nv] === 0) {
ch[nv] = 1;
dfsPath.push(nv);
DFS(nv);
}
}
}
DFS(v);
}
function getBFSPath(v) {
let q = [];
let ch = Array.from({ length: n + 1 }, () => 0);
ch[v] = 1;
bfsPath.push(v);
q.push(v);
while (q.length) {
const v = q.shift();
for (let i = 0; i < graph[v].length; i++) {
const nv = graph[v][i];
if (ch[nv] === 0) {
ch[nv] = 1;
bfsPath.push(nv);
q.push(nv);
}
}
}
}
getDFSPath(v);
getBFSPath(v);
console.log(dfsPath.join(" "));
console.log(bfsPath.join(" "));
입력 받은 그래프를 연결 되어 있는 노드 배열을 for문으로 돌면서 인접 리스트로 만든다.
DFS는 각 노드에 연결되어 있는 노드를 순회하면서 (graph[v].length) 다음 노드(nv)가 방문하지 않은 노드인 경우(if(ch[nv] === 0) 해당 노드로 바로 이동(DFS(nv))한다.
반면 BFS는 각 노드에 연결되어 있는 노드를 순회하면서 다음 노드가 방문하지 않은 노드인 경우 q에 넣고 대기한다. 동일 레벨에 있는 노드들을 모두 방문하고 난 다음에야 q에 넣어둔 노드(연결되어 있는 노드)를 방문한다.
반응형
'Algorithm > BOJ' 카테고리의 다른 글
[알고리즘/백준/2667] 단지 번호 붙이기 (1) | 2023.05.23 |
---|---|
[알고리즘/백준/1325] 효율적인 해킹(BFS, JavaScript, 백준 Nodejs로 풀 때 유의사항) (4) | 2023.05.22 |
[알고리즘/백준/2178] 미로탐색(BFS, 최단거리) (1) | 2023.05.22 |
[알고리즘/백준/11725] 트리의 부모 찾기(DFS, BFS, 백준 console 시간 초과 해결) (0) | 2023.05.21 |
[알고리즘/백준/2606] 바이러스 (0) | 2023.05.21 |