백준 2644 촌수계산

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

https://www.youtube.com/watch?v=zSMwRFuk8jA

문제 이해과정

• 나같은 알고리즘 초보는 언제나 생각해야한다 코드를 치기 전에 어떻게 해결할 것인가?
• 친척관계를 나타낼때 나를 기준으로 하면 아빠는 1촌 할아버지는 2촌 이렇게 연결된다
• 두 사람의 관계가 몇촌인지 정수로 출력해 주면 되는 문제이다
• [from, to] 형식으로 입력이 주어진다
• 각 사람들이 누구와 연결되어 있는지 인접리스트로 구현하기로 했다
• 주어진 한 사람을 start 한 사람을 end로 지정해 주기로 했다
• start를 기준으로 각 사람마다 얼마나 거슬러 올라갔는지 배열을 만들어 주었다
• 인접리스트를 적어놓고 어떻게 접근할지를 생각해 보았다

• 인접리스트의 형태와 그래프를 보며 어떤식으로 해결할지에 대해 그려보았다
• 나도 그림을 잘그리고싶어!!

const fs = require("fs");
//const input = fs.readFileSync("/dev/stdin").toString().trim().split("\n");
let input = fs.readFileSync("example.txt", "utf8").toString().split('\n');


const n = +input[0]

const [x, y] = input[1].split(' ')
const datas = input.slice(3).map(el => el.split(' ').map(Number))


const nodes = Array.from({ length: n + 1 }, () => [])
const depth = Array.from({ length: n + 1 }, () => 0)
datas.forEach(([from, to]) => {
    nodes[from].push(to)
    nodes[to].push(from)
})
//여기까지 인풋 데이터 가공의 과정을 거쳤다
//스터디 조원분께서 말씀해 주셨던 slice로 배열을 잘라서 반환하는 방법을 사용해보았다



const bfs = (start, end) => {
    depth[start] = 1
    const queue = []
    queue.push(start)
    while (queue.length != 0) {
        let cur_v = queue.shift()
        for (const node of nodes[cur_v]) {
            if (depth[node] == 0) {
                queue.push(node)
                depth[node] = depth[cur_v] + 1
            }
        }
    }
  /*
  그동안 했던 단순히 탐색해 주는것과 거의 동일하게 모든곳을 탐색하는데
  사실 end의 탐색을 마쳤다면 거기서 멈춰주는 방법이 더 좋을 것 같다는 생각이 들었다.
  
  리펙토링을 하며 visited배열을 없애주고 어차피 depth의 인덱스가 0이면 방문하지 않았다는 의미와 동일해서
  그 점을 이용하여 탐색과 카운트를 동시에 공격과 방어를 동시에 하듯 해주었고,
  */
    if (depth[end] === 0) {
        return -1
    } else {
        return depth[end] - depth[start];
    }
}
//if문을 통해 각 인덱스의 값을 이용하여 문제가 원하는 답을 내어드렸다 이상

console.log(bfs(x, y))

//이상 깔끔한 코드로 마무리 해보겠다
const fs = require("fs");
//const input = fs.readFileSync("/dev/stdin").toString().trim().split("\n");
let input = fs.readFileSync("example.txt", "utf8").toString().split('\n');


const n = +input[0]

const [x, y] = input[1].split(' ')
const datas = input.slice(3).map(el => el.split(' ').map(Number))


const nodes = Array.from({ length: n + 1 }, () => [])
const depth = Array.from({ length: n + 1 }, () => 0)
datas.forEach(([from, to]) => {
    nodes[from].push(to)
    nodes[to].push(from)
})

const bfs = (start, end) => {
    depth[start] = 1
    const queue = []
    queue.push(start)
    while (queue.length != 0) {
        let cur_v = queue.shift()
        for (const node of nodes[cur_v]) {
            if (depth[node] == 0) {
                queue.push(node)
                depth[node] = depth[cur_v] + 1
            }
        }
    }

    if (depth[end] === 0) {
        return -1
    } else {
        return depth[end] - depth[start];
    }
}

console.log(bfs(x, y))