정다윤 풀이
const filePath = process.platform === "linux" ? "/dev/stdin" : "input.txt"; const input = require("fs") .readFileSync(filePath) .toString() .trim() .split("\n"); const N = Number(input.shift()); const graph = [...new Array(N + 1)].map(() => []); const parents = [...new Array(N + 1)]; // 부모 노드를 기록하는 배열 for (let edge of input) { let [start, end] = edge.split(" ").map(Number); graph[start].push(end); graph[end].push(start); } // bfs 사용 function bfs() { const queue = []; queue.push(1); // 1번 노드의 자식이 2,3이었다면, // 2,3의 부모노드는 1이므로 1을 기록한다. while (queue.length) { const start = queue.shift(); for (let end of graph[start]) { if (!parents[end]) { parents[end] = start; queue.push(end); } } } } bfs(); // 2번 노드의 부모부터 출력 console.log(parents.slice(2).join("\n"));
김민수 풀이
let input = require('fs').readFileSync(__dirname + "/../input.txt").toString().trim().split("\n"); // let input = require('fs').readFileSync("/dev/stdin").toString().trim().split("\n"); const [[N], ...nodes] = input.map((e) => e.split(' ').map(Number)); const graph = Array.from({ length: N + 1 }, () => []); const visited = Array(N + 1).fill(false); const parent = Array(N + 1); const queue = [1]; for (const [a, b] of nodes) { graph[a].push(b); graph[b].push(a); } while (queue.length) { const node = queue.shift(); for (const x of graph[node]) { if (!visited[x]) { visited[x] = true; parent[x] = node; queue.push(x); } } } let result = []; for (let i = 2; i < N + 1; i++) { result.push(parent[i]) } console.log(result.join('\n'));