https://www.acmicpc.net/problem/2644
2644번: 촌수계산
사람들은 1, 2, 3, …, n (1 ≤ n ≤ 100)의 연속된 번호로 각각 표시된다. 입력 파일의 첫째 줄에는 전체 사람의 수 n이 주어지고, 둘째 줄에는 촌수를 계산해야 하는 서로 다른 두 사람의 번호가 주어
www.acmicpc.net
작성한 코드
// 2644
const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "Beakjoon/Silver/test.txt";
let input = fs.readFileSync(filePath).toString().trim().split("\n");
const n = parseInt(input.shift(), 10);
const [start, end] = input.shift().split(" ").map(Number);
const m = parseInt(input.shift(), 10);
const arr = input.map((item) => item.split(" ").map(Number));
const makeGraph = (arr) => {
const graph = {};
for (const item of arr) {
const [first, second] = item;
graph[first] ? graph[first].push(second) : (graph[first] = [second]);
graph[second] ? graph[second].push(first) : (graph[second] = [first]);
}
for (let i = 1; i <= n; i++) {
if (!graph[i]) graph[i] = [];
}
return graph;
};
const solution = () => {
const graph = makeGraph(arr);
const bfs = (root) => {
const visited = new Array(n + 1).fill(-1);
const queue = [root];
visited[root] = 0;
while (queue.length) {
const node = queue.shift();
for (const n of graph[node]) {
if (visited[n] === -1) {
queue.push(n);
visited[n] = visited[node] + 1;
}
if (n === end) {
return visited[n];
}
}
}
return -1;
};
return bfs(start);
};
console.log(solution());

'알고리즘 > 백준' 카테고리의 다른 글
| [JavaScript/BFS] 백준 실버 1 : 1697 - 숨바꼭질 (0) | 2023.09.19 |
|---|---|
| [JavaScript/BFS] 백준 골드 5 : 7569 - 토마토 (0) | 2023.09.18 |
| [JavaScript/BFS] 백준 실버 1 : 2667 - 단지번호붙이기 (0) | 2023.09.12 |
| [JavaScript/DFS] 백준 실버 3 : 10451 - 순열 사이클 (0) | 2023.09.08 |
| [JavaScript/DFS/BFS] 백준 실버 1 : 1260 - DFS와 BFS (0) | 2023.09.07 |