[백준] 촌수계산 (javascript)

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

2644번: 촌수계산

 

🤔 해결방법

1. 필요한 변수들 할당하고 그래프 생성

2. 촌수를 계산할 a의 인접노드를 차례로 순회하며 해당 촌수가 0이면 a의 촌수 +1로 업데이트 후 재귀

3. 촌수를 계산받을 사람의 촌수를 출력, 이 때 0이라면 -1을 출력

 

 

🔑 풀이

일반적으로 노드를 이동할 때 조건이 붙으면 DFS, 최단거리를 구하거나 인접노드를 공통적으로 처리해야할 때는 BFS를 사용한다는 것을 알게 되었다.

따라서 이 문제는 부모노드에서 자식노드로 향하는 최단거리 구하는 문제와 같으므로 BFS를 사용하는 것이 정석이라고 할 수 있겠다.

하지만 나는 코드가 좀 더 짧은 DFS를 사용했다.😁

 

예제 1번을 그래프로 표현하면 다음과 같고 7에서 3까지의 최단거리는 3이므로 3을 출력하면 되는 것이다.

 

 

먼저 필요한 변수들을 저장하고 그래프를 생성했다.

const input = require("fs")
    // .readFileSync("/dev/stdin")
    .readFileSync(__dirname + "/input.txt")
    .toString()
    .trim()
    .split("\n");

  const n = parseInt(input[0]); // 전체 사람 수
  const [a, b] = input[1].split(" ").map(Number); // 촌수를 계산할 사람
  const m = parseInt(input[2]); // 관계의 개수

  // 그래프 생성
  let graph = [...Array(n + 1)].map(() => []);
  for (let i = 3; i <= m + 2; i++) {
    let [x, y] = input[i].split(" ").map(Number);
    graph[x].push(y);
    graph[y].push(x);
  }

 

그리고 방문 여부와 촌수를 저장하기 위해 0으로 채워진 빈 배열 visited를 만든다.

이후 a의 인접노드를 차례로 순회하며 해당 촌수가 0이면 a의 촌수 +1로 업데이트한다.

 

let visited = Array(n + 1).fill(0); // 방문 여부 및 촌수 저장 배열

  // DFS 함수
  function dfs(man) {
    for (const adjacentNode of graph[man]) {
      // 방문하지 않은 인접노드면
      if (visited[adjacentNode] === 0) {
        visited[adjacentNode] = visited[man] + 1; // 현재 노드의 촌수 + 1로 업뎃
        dfs(adjacentNode);
      }
    }
  }

 

최종적으로 visited[b] 를 출력하면 되는데 예제 1번에서는 visited = [0, 2, 1, 3, 0, 0, 0, 2, 2, 2] 가 되고 visited[3]인 3이 출력된다.

촌수를 계산받을 사람의 촌수가 0이라면 -1이 출력되므로 예제 2번은 -1이 출력되겠다.

최종 정답 코드는 다음과 같다.

 

const input = require("fs")
    .readFileSync("/dev/stdin")
    .toString()
    .trim()
    .split("\n");

  const n = parseInt(input[0]); // 전체 사람 수
  const [a, b] = input[1].split(" ").map(Number); // 촌수를 계산할 사람
  const m = parseInt(input[2]); // 관계의 개수

  // 그래프 생성
  let graph = [...Array(n + 1)].map(() => []);
  for (let i = 3; i <= m + 2; i++) {
    let [x, y] = input[i].split(" ").map(Number);
    graph[x].push(y);
    graph[y].push(x);
  }

  console.log(graph[9]);

  let visited = Array(n + 1).fill(0); // 방문 여부 및 촌수 저장 배열

  // DFS 함수
  function dfs(man) {
    for (const adjacentNode of graph[man]) {
      // 방문하지 않은 인접노드면
      if (visited[adjacentNode] === 0) {
        visited[adjacentNode] = visited[man] + 1; // 현재 노드의 촌수 + 1로 업뎃
        dfs(adjacentNode);
      }
    }
  }

  dfs(a);

  // 촌수를 계산받을 사람의 촌수가 0이라면 -1 출력
  if (visited[b] === 0) console.log(-1);
  else console.log(visited[b]);