-
[백준/javascript] 1260 DFS와 BFS카테고리 없음 2023. 2. 25. 15:00
const fs = require("fs"); // let stdin = fs.readFileSync("./input.txt").toString(); let stdin = fs.readFileSync("/dev/stdin").toString(); // const input = stdin.split("\n").map((v) => v.split(" ").map(Number)); const [a, ...b] = input; // const [N, A, operators] = input; const [n, m, v] = [...a]; class Graph { constructor() { this.adjacentList = {}; } addEdge(v1, v2) { if (!this.adjacentList[v1]) { this.adjacentList[v1] = []; } if (!this.adjacentList[v2]) { this.adjacentList[v2] = []; } this.adjacentList[v1].push(v2); this.adjacentList[v2].push(v1); } sort() { const adjacentList = this.adjacentList; for (let key in adjacentList) { adjacentList[key].sort((a, b) => a - b); } } dfs(v) { const result = []; const visited = {}; const adjacentList = this.adjacentList; function dfsRecurr(v) { if (!v) return null; visited[v] = true; result.push(v); if (adjacentList[v]) {//이 if문이 있어야 정점에 간선연결이 되어있지 않은 경우를 대비할 수 있다. adjacentList[v].forEach((element) => { if (!visited[element]) { return dfsRecurr(element); } }); } } dfsRecurr(v); return result; } bfs(v) { const queue = [v]; const result = []; const visited = {}; const adjacentList = this.adjacentList; let currentV; visited[v] = true; while (queue.length !== 0) { currentV = queue.shift(); result.push(currentV); if (adjacentList[currentV]) {//정점에 간선연결이 되어있지 않은 경우 대비 adjacentList[currentV].forEach((el) => { if (!visited[el]) { visited[el] = true; queue.push(el); } }); } } return result; } } const graph = new Graph(); b.map((el) => graph.addEdge(...el)); graph.sort(); console.log(graph.dfs(v).join(" ")); console.log(graph.bfs(v).join(" "));
어마어마하게 오래 걸린 ㅎㅎ... 이제 DFS와 BFS 열심히 연습하면 된다 ㅎㅎ..