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

1ilsang
클라이밍 하실래염?
#algorithm#goorm#graph#sort
Published

cover

문제 링크

양방향 그래프에서 시작 점으로부터 더 이상 갈 수 없을 때까지 이동한 뒤 출력하면 되는 문제다.

접근법

// 양방향 그래프
map[i].push(j); // i 노드가 j 노드로 방향성을 가지고 있다.
map[j].push(i); // j 노드가 i 노드로 방향성을 가지고 있다.
console.log(map);
// { i: [j, ...], j: [i, ...] }

양방향 그래프이기 때문에 그래프를 만들 때 좌우 둘 다 추가해 준다.

각 정점에서 방문하지 않았던 번호가 낮은 노드로 이동하기 때문에 각 정점의 값은 정렬되어 있어야 한다.

[100, 30, 200].sort();
// [100, 200, 30]

유의. 자바스크립트에서 sort함수에 비교함수 콜백을 작성하지 않으면 ASCII값을 기준으로 정렬한다.

따라서 "문자"로 비교하기 때문에 30, 100, 200이 아닌 첫 번째 문자의 아스키 값의 우선순위에 따라 100, 200, 30이 출력된다.

// a, b중 큰 값은 뒤로(+) 작은 값은 앞으로(-) 가게 된다.
[100, 30, 200].sort((a, b) => a - b);
// [30, 100, 200]
 
// 0이므로 a, b는 서로 변경되지 않는다.
[100, 30, 200].sort((a, b) => 0);
// [100, 30, 200]
 
// a, b중 큰 값은 앞으로(-) 작은 값은 뒤로(+)가게 된다.
[100, 30, 200].sort((a, b) => b - a);
// [200, 100, 30]

따라서 비교 함수 콜백을 통해 정렬의 우선순위를 먼저 지정해야 한다.

  • 콜백 함수의 리턴값이 0보다 작은 경우(음수) a를 b보다 낮은 인덱스로 정렬한다(a가 먼저 오므로 오름차순이 됨).
  • 콜백 함수의 리턴값이 0인 경우 a와 b를 서로 변경하지 않고 다른 요소에 대해 정렬한다(현재 두 값으로는 비교 X).
  • 콜백 함수의 리턴값이 0보다 큰 경우(양수) a를 b보다 높은 인덱스로 정렬한다(b가 먼저 오므로 내림차순이 됨).

방문한 횟수는 방문(메모) 배열에 값을 추가해 나가다 마지막에 배열 길이를 출력하면 된다.

정리

  1. 양방향 그래프를 그린다.
  2. 메모 배열을 활용해 방문 시 체크해 준다.
  3. 마지막 노드와 메모 배열의 길이를 출력한다.
  4. sort 함수는 문자(ASCII)를 기준으로 정렬하기 때문에 유의해야 한다.

최종 코드

const readline = require('readline');
let rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});
const input = [];
rl.on('line', (line) => {
  input.push(line);
});
 
rl.on('close', () => {
  const map = {};
 
  const [n, m, k] = input[0].split(' ').map(Number);
  for (const line of input.slice(1)) {
    const [i, j] = line.split(' ').map(Number);
    if (!map[i]) map[i] = [];
    if (!map[j]) map[j] = [];
    // 양방향 그래프 생성
    map[i].push(j);
    map[j].push(i);
  }
 
  // k 노드부터 출발할 예정이므로 메모와 last 값을 초기화한다.
  const memo = [k];
  let last = k;
  while (true) {
    // 현재 노드의 값이 없다면 이어진 정점이 없으므로 탈출한다.
    if (!map[last]) break;
    const next = map[last]
      .filter((node) => !memo.includes(node)) // 방문한 적이 없는 값들만 필터링한다.
      .sort((a, b) => a - b)[0]; // 방문하지 않은 정점들을 오름차순 정렬해 첫 번째 값을 꺼낸다.
    if (!next) break; // next가 없다면 해당 노드에서 갈 수 있는 모든 정점을 방문한 상태이므로 종료한다.
    last = next; // 마지막 노드를 갱신한다.
    memo.push(last); // 메모에 마지막 노드를 추가한다.
  }
  console.log(`${memo.length} ${last}`);
});
📮 이 포스트에 관심 있으신가요? 이슈를 남겨주세요! 👍
☕ 소주 한 잔 후원하기
(예금주: 이상철)tosskakao