[ 백준_2644 ] 촌수계산 ( bfs - 자바스크립트 )

문제

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

2644번: 촌수계산

 

How to Solve ?

 

[1] BFS

특정 인원과의 촌수를 찾는 다는 것은, 어떻게 보면 최단거리로 갔을 때만 얻어 질 수 있는 개념 이라 생각하여 "BFS"를 사용했습니다.

 

[1-1] 인접 행렬 만들기

 

인접 리스트가 더 효과적이라고 생각은 하지만 행렬 구현에 익숙해져서 인접행렬을 makeConnection 함수를 통해 구현 하였습니다.

  [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
  [0, 0, 1, 1, 0, 0, 0, 0, 0, 0],
  [0, 1, 0, 0, 0, 0, 0, 1, 1, 1],
  [0, 1, 0, 0, 0, 0, 0, 0, 0, 0],
  [0, 0, 0, 0, 0, 1, 1, 0, 0, 0],
  [0, 0, 0, 0, 1, 0, 0, 0, 0, 0],
  [0, 0, 0, 0, 1, 0, 0, 0, 0, 0],
  [0, 0, 1, 0, 0, 0, 0, 0, 0, 0],
  [0, 0, 1, 0, 0, 0, 0, 0, 0, 0],
  [0, 0, 1, 0, 0, 0, 0, 0, 0, 0],

 

[1-2] 촌수 계산

 

연결된 사람을 따라가면서, 만날 수 있는 경우에는 bfs를 할 때 마다 카운트를 올려준다.

 

만약, 끝까지 했음에도 결과를 얻지 못하면 "-1" 을 출력한다.

 

 

전체 코드

 
 
function makeConnection(n, relation) {
  const arr = Array.from(Array(n + 1), () => Array(n + 1).fill(0));
 
  for (let i = 0; i < relation.length; i++) {
    const [prev, next] = relation[i];
 
    arr[prev][next] = 1;
    arr[next][prev] = 1;
  }
 
  return arr;
}
 
function bfs(start, end, visited, connection, answer) {
 
  const queue = [start, 0];
  visited[start] = 1;
 
  while (queue.length) {
  
    start = queue.shift();
    let count = queue.shift();
	// 원하는 인원과의 연결 고리를 찾으면
    if (start === end) {
      answer = count;
      break;
    } else {
      // 인접 행렬을 순환하면서 자신과 연결된 가장 가까운 인원을 탐색
      for (let i = 1; i <= n; i++) {
        // 방문한 기록이 없고, 연결이 되어 있으면
        if (connection[start][i] === 1 && !visited[i]) {
          // 방문 처리를 해주고,
          visited[i] = 1;
          // bfs를 실행.
          queue.push(i, count + 1);
        }
      }
    }
    
  }
  
  return answer;
}
 
function solution(n, relation) {
 
  let answer = 0;
  
  const [a, b] = [7, 3];
  const connection = makeConnection(n, relation);
  const visited = Array(n + 1).fill(0);
 
  answer = bfs(a, b, visited, connection, answer);
  
  // 반환된 값이 없다면, 연결고리가 없음을 의미
  answer === 0 ? console.log(-1) : console.log(answer);
  
}
 
 
// local input
// const n = 9;
// const m = 7;
// const relation = [
//   [1, 2],
//   [1, 3],
//   [2, 7],
//   [2, 8],
//   [2, 9],
//   [4, 5],
//   [4, 6],
// ];
 
// solution(n, relation);