[JavaScript] 구름톤 챌린지 3주차 코딩테스트 : 작은 노드

📌  문제

📌  입력

📌  출력 및 예제

---

📌  풀이

알아야 하는 것

• 그래프 만들기

구할 것

• 데이터 가공
  • 입력값 첫 줄에 주어지는 노드의 개수, 간선의 개수, 시작 노드의 번호를 shift로 따 와 각각 numOfNode, numOfEdge, startNodeNum에 할당한다.
  • 나머지 input 값은 그래프에 넣어줘야 하기 때문에 모두 number로 형 변환을 한다.
• 그래프 만들기
  • numOfNode+1 길이를 가진 배열을 만들어 graph를 만들고, 똑같은 크기이지만 false로 fill한 visited를 만들어준다.
  • input의 한 줄을 from, to로 구조 분해 할당 하여 graph에 인덱스에 맞게 넣어준다.
  • 인덱스와 노드 번호 수를 일치 시키기 위해 graph의 배열 크기를 +1 한 것
• 계산하기
  • queue에 시작 노드의 번호를 넣어주고 방문 처리를 한다.
  • 문제에서 시작 노드도 방문한 것으로 간주한다고 했기 때문에, 방문한 노드 개수를 셀 numOfVisitedNodes를 1로 초기화한다.
  • 똑같이 마지막 노드의 번호도 startNodeNum으로 초기화 한다.
  • 처음 방문한 노드가 끝일 수도 있다. 이 경우에는 처음 방문한 노드와 그 개수를 반환해야 하기 때문이다.
  • while문을 돌 때, 방문할 수 있으면서 가장 번호가 작은 노드로 이동해야 한다는 조건이 있다.
    • 이를 위해 minNextNode를 2001로 할당했다. (입력 범위 2000이 최대) Infinity로 줘도 될 것 같다.
    • 현재 시작 노드와 이어진 노드들 중 방문하지 않은 것들만 확인했을 때, 2001보다 작은 노드 번호를 가진 노드로 가야 한다. Math.min을 써서 더 작은 노드 번호를 택하게 한다.
    • 따라서 더 작은 노드 번호가 2001이 아니라면 방문할 수 있으니 방문하고, 방문했으니 방문한 노드 수를 1 추가하고, queue에 다시 넣어 돌림과 동시에 마지막 방문한 노드의 번호도 해당 노드 번호로 초기화 한다.
• 시작 노드도 방문한 것으로 간주하는 점, 방문할 수 있으면서 번호가 가장 작은 노드로 가야 하는 점이 문제의 키 포인트인 것 같다.

const readline = require('readline');
let rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout,
});
let input = [];
let numOfNode, numOfEdge, startNodeNum; // 노드 개수, 간선 개수, 시작 노드 번호 변수 추가

rl.on('line', (line) => {
    input.push(line);
    if (input.length === 1) {
        [numOfNode, numOfEdge, startNodeNum] = line.split(" ").map(Number);
    }
    if (input.length === numOfEdge + 1) {
        rl.close();
    }
});

rl.on('close', () => {
	let [numOfNode, numOfEdge, startNodeNum] = input.shift().split(" ").map(Number);
	input = input.map(v => v.split(" ").map(Number));

	const graph = Array.from(Array(numOfNode+1), () => []);
	const visited = Array.from(numOfNode+1).fill(false);
	
	for (let [from, to] of input) {
		graph[from].push(to)
		graph[to].push(from)
	}
	
	const queue = [];
	queue.push(startNodeNum);
	visited[startNodeNum] = true;
	let numOfVisitedNodes = 1;
	let lastVisitedNode = startNodeNum; 
	
	while (queue.length) {
		const cur = queue.shift();
		let minNextNode = 2001; 
		for (let next of graph[cur]) {
			if (!visited[next]) {
				minNextNode = Math.min(minNextNode, next); 
			}
		}
		if (minNextNode !== 2001) { 
			visited[minNextNode] = true;
			numOfVisitedNodes += 1;
			queue.push(minNextNode);
			lastVisitedNode = minNextNode; 
		}
	}
	
	console.log(numOfVisitedNodes, lastVisitedNode);
});