[백준] 6118번 node.js 개인 풀이, 숨바꼭질 javscript풀이

문제 설명

링크

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

 

한국어 문제가 다소 가독성이 떨어졌던 문제..

문제에서 요구하는 결과는 다음과 같다.

 

1. 헛간의 개수는 N개, 헛간끼리 연결된 길의 개수= 관계= 간선은 M개

2. 1번 헛간에서 가장 멀리 떨어진 헛간을 찾아야하며, 그 헛간의 번호, 1번 헛간으로부터의 거리, 그리고 거리 비용이 같은 헛간의 수를 출력해야 한다.

3. 헛간 간의 경로는 항상 양방향으로 연결되어 있다.

 

나는 인접리스트와 BFS를 이용하여 문제를 접근했다.

헛간과 길 정보를 가지고 그래프를 구성하고, BFS를 사용해 특정 시작점(1번헛간) 으로부터 모든 노드까지의 거리를 계산한다. 보통은 최단 거리를 찾는데 쓰지만 그 반대의 경우도 BFS를 쓰기 유용하다.

 

DFS를 사용해도 되지만 DFS를 사용할 경우재귀 호출이 많이 발생할 수 있기 때문에 사용하지 않았다.

 

밑에 코드 설명

1. 인접리스트 생성 (헷갈리지 않기 위해 n+1개를 생성하여 0행 0열은 무시)

2. BFS 함수 작성 

   - queue배열에 방문할 노드를 push로 넣고, shift로 앞에서부터 하나씩 빼준다.

   - 방문한 노드일 경우 스킵, 새로 방문한 곳은 인접한 노드를 queue에 넣어주고 방문 체크

   - visitCost 1차원 배열에 방문의 뜻으로 거리 비용을 넣어준다. 이 거리비용은 이전 노드의 거리비용+1이다.

3. visitCost 배열을 돌면서 결과 구하기

 

 

 

문제 풀이

풀이

const fs = require('fs');
const [nm, ...ms] = fs
  .readFileSync(
    process.platform === 'linux' ? '/dev/stdin' : __dirname + '/input.txt'
  )
  .toString()
  .trim()
  .split('\n')
  .map((el) => el.trim().split(' ').map(Number));

const [n, m] = nm;

//방문한 노드의 거리비용을 넣기 위한 1차원 배열
const visitCost = Array.from({ length: n + 1 }).fill(null);

//인접리스트 생성
const graph = Array.from({ length: n + 1 }, () => []);
ms.forEach(([u, v]) => {
  graph[u].push(v);
  graph[v].push(u);
});

const bfs = (graph, start, visitCost) => {
  const q = [];
  q.push(start);
  visitCost[start] = 0;

  while (q.length !== 0) { 
    const node = q.shift();
    for (const curr of graph[node]) {
      if (visitCost[curr] === null) {
        q.push(curr);
        visitCost[curr] = visitCost[node] + 1;
      }
    }
  }
};

bfs(graph, 1, visitCost);
let max = 0; //가장 거리가 먼 헛간 거리
let fartestNode; // 가장 거리가 먼 노드
let count = 1; // 같은 거리의 헛간 개수
for (let i = 1; i < n + 1; i++) {
  if (visitCost[i] > max) { // 더 먼 헛간이 나오면
    max = visitCost[i];
    fartestNode = i;
    count = 1;
  } else if (visitCost[i] === max) { //max와 같은 거리의 헛간 개수 
    count += 1;
  }
}
console.log(fartestNode, max, count);

결과