[구름톤 챌린지] 작은 노드 (JS)

hhkim·2023년 8월 31일
0

Algorithm - JavaScript

목록 보기
119/188
post-thumbnail

풀이 과정

  1. 노드 개수만큼의 visited 배열 만들기
  2. 노드를 키, 간선 배열을 값으로 하는 객체 만들기
  3. 간선에 대해 반복하면서 양방향 노드에 대해 간선 추가
  4. 각 노드에 대해 간선 오름차순 정렬
  5. 시작 노드부터 무한 반복
  6. 노드 방문 표시하고 방문한 노드 개수 +1
  7. 현재 노드에 연결된 노드 중 가장 작은 노드 방문 여부 확인
    방문하지 않았다면 현재 노드 갱신 => 6~7 반복
  8. 더이상 갈 수 있는 노드가 없다면 반복문 탈출

코드

const readline = require('readline');
let rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});
let input = [];
let N, M, K;
rl.on('line', (line) => {
  input.push(line.trim());
  [N, M, K] = input[0].split(' ').map(Number);
  if (input.length === M + 1) {
    rl.close();
  }
});

rl.on('close', () => {
  const visited = Array(N + 1).fill(false);
  const edges = [];
  for (let i = 1; i <= M; ++i) {
    edges.push(input[i].split(' ').map(Number));
  }
  const nodes = {};
  for (const [n1, n2] of edges) {
    nodes[n1] = nodes[n1] ? [...nodes[n1], n2] : [n2];
    nodes[n2] = nodes[n2] ? [...nodes[n2], n1] : [n1];
  }
  for (let i = 1; i <= N; ++i) {
    if (!nodes[i]) continue;
    nodes[i].sort((a, b) => a - b);
  }

  let curr = K;
  let count = 0;

  while (true) {
    ++count;
    visited[curr] = true;
    const prev = curr;
    if (!nodes[curr]) break;
    for (const node of nodes[curr]) {
      if (visited[node]) continue;
      curr = node;
      break;
    }
    if (prev === curr) break;
  }

  console.log(count, curr);
  process.exit();
});

🤔

문제 보고 긴장했는데 생각보다 쉽게 풀렸다.
노드에 연결된 노드 목록이 중복되는 문제가 있어서 nodes의 값을 set으로 바꿔야하나 하다가 오늘은 여기서 마무리하기로 했다..

0개의 댓글