[백준 node.js] 2644번_촌수계산

백준 BFS 알고리즘 2644번_촌수계산

난이도 : 실버II

 

문제설명

입출력

 

문제 풀이 :  주어진 사람의 번호가 서로 몇 촌인지 계산하면 된다. 촌수는 부모가 같으면 형제, 즉 같은 촌수이다.

이를 좀더 생각하면 형제는 촌수를 계산할 필요없고 부모일때만 계산해주면 된다. 즉 최단경로 문제처럼 거리가 같으면 계산을 안하고 거리가 다를때 계산을 해주는 BFS 유형인것을 알 수 있다. BFS를 이용하여 촌수를 계산하면된다.

 

연결된 노드만 파악하면 되기 때문에 인접그래프 형식으로 풀었다.

 

//실버2 촌수계산
const solution = (p, q) => {
  //시작 촌수 p삽입
  let start = [p];
  let cnt = 0;
  while (start.length !== 0) {
    cnt += 1; //촌수 카운트
    //BFS는 최적의 경로를 구하기 때문에
    //연결된 노드를 전부 순회후 다음 노드를 순회해야한다.
    let len = start.length;

    //배열의 길이만큼 수행한다 즉, 같은 촌수에 해당하는 노드 탐색
    for (let j = 0; j < len; j++) {
      //배열에 담긴 같은 노드를 하나씩 가져와 탐색
      let tmp = start.shift();
      visited[tmp] = true; //해당 노드 방문처리
      //tmp와 연결된 노드 정보를 가져옴
      for (let z of graph[tmp]) {
        //연결된 노드가 아직 방문 처리안됬다면 탐색하지 않은 노드이다.
        if (visited[z] === false) {
          //연결된 노드가 찾는 노드(촌수)라면 리턴
          if (z === q) {
            return cnt;
          }
          //연결된 노드를 배열에 넣어줌
          start.push(z);
        }
      }
    }
  }
  //촌수가 없을시
  return -1;
};

const readline = require("readline");
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

let input = [];
let graph = [];
let visited = [];
rl.on("line", function (line) {
  //여러줄 입력
  input.push(line);
}).on("close", function () {
  let n = Number(input.shift()); // 전체사람수 n
  graph = Array.from(Array(n + 1), () => Array()); //n만큼 인접그래프 생성
  visited = new Array(n + 1).fill(false); //방문처리
  let [p, q] = input //파악해야하는 촌수쌍
    .shift()
    .split(" ")
    .map((el) => Number(el));
  let m = Number(input.shift()); //부모자식 관계 m

  for (let i = 0; i < m; i++) {
    let [x, y] = input //부모 자식관의 관계
      .shift()
      .split(" ")
      .map((el) => Number(el));
    graph[x].push(y); //인접그래프 형식으로 추가
    graph[y].push(x);
  }
  let result = solution(p, q);
  console.log(result);
  process.exit();
});

*DFS와 BFS의 가장 큰 차이점은 노드들을 이동할때 이동 단계마다 가중치가 붙거나 조건이 있으면 DFS!

최단거리를 구해야하거나 인접노드들을 공통적으로 처리해야할때는 BFS! 라는 것을 기억하고 있으면 좋다