[백준알고리즘] 알고리즘 연습 - 2644

2644 - 촌수계산

https://www.acmicpc.net/problem/2644

let fs = require('fs');
let input = fs.readFileSync('/dev/stdin').toString().split('\n');

let n = Number(input[0]);
let target = input[1].split(" ").map((num) => Number(num));
let conn = [];
for(let i=3; i<input.length; i++) {
    if (input[i] != "") {
        conn.push(input[i].split(" ").map((num) => Number(num)));
    }
}

function answer(target, input) {
    let visited = new Array(n+1).fill(false);
    let queue = [];
    input.forEach((i) => {
        if (i[0] == target[0]) {
            queue.push([i[0], i[1], 1]);
            visited[i[0]] = true;
        }
        else if (i[1] == target[0]) {
            queue.push([i[1], i[0], 1]);
            visited[i[1]] = true;
        }
    })
    let idx = 0;
    let ans = -1;
    while(queue.length != idx) {
        let [x, y, val] = queue[idx++];
        if (y == target[1] || x == target[1]) {
            ans = val;
            break;
        }
        if (visited[y]) continue;
        visited[y] = true;
        input.forEach((i) => {
            if (i[0] == y) queue.push([i[0], i[1], val+1]);
            else if (i[1] == y) queue.push([i[1], i[0], val+1]);
        })
    }
    return ans;
}

console.log(answer(target, conn));

처음에 dfs로 할랬는데 ㄴ너어무 안돼서 bfs로 수정했다.
dfs도 언젠가 도전쓰...