[구름톤 챌린지] 작은 노드
1ilsang
클라이밍 하실래염?
Published
양방향 그래프에서 시작 점으로부터 더 이상 갈 수 없을 때까지 이동한 뒤 출력하면 되는 문제다.
접근법
// 양방향 그래프
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가 먼저 오므로 내림차순이 됨).
방문한 횟수는 방문(메모) 배열에 값을 추가해 나가다 마지막에 배열 길이를 출력하면 된다.
정리
- 양방향 그래프를 그린다.
- 메모 배열을 활용해 방문 시 체크해 준다.
- 마지막 노드와 메모 배열의 길이를 출력한다.
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}`);
});