[구름 먼데이 챌린지] 구름이의 여행

문제

구름이가 사는 구름 나라는 N개의 섬으로 이루어져 있다. 각 섬에는 1부터 N까지의 번호가 붙어 있고, 구름 나라는 사람들이 섬과 섬 사이를 편하게 이동할 수 있도록 다리를 M개 설치했다. 설치된 다리들은 아래 특징들을 만족한다.

• 모든 다리는 양방향으로 이동할 수 있다.
• 서로 다른 두 섬을 잇는 다리는 최대 하나이다.
• 다리가 잇는 두 섬은 항상 다른 섬이다.

구름이는 1번 섬에서 출발해서 N번 섬으로 가려고 하는데, 통과하는 다리의 개수가 K개 이하가 되길 원한다. 구름이를 도와 1번 섬에서 N번 섬까지 K개 이하의 다리를 이용해 도착할 수 있는지를 판별해보자.

 

해결 방안

1번 다리에서부터 시작하기에 distances 배열을 가지고 각각 최소단위로 1씩 증가시켜서 각 섬마다의 최소 거리를 넣어주는 배열을 선언했다. 인접리스트 방식으로 그래프를 구현했고 q 배열에 bfs방식으로 섬을 탐색해가며 최소거리값을 구해나갔다.

 

자바스크립트 코드

// Run by Node.js
const readline = require('readline');
let input = [];
let rl = readline.createInterface({ input: process.stdin });
rl.on('line', (l) => {
	input.push(l);
}).on('close',()=>{
	const [n,m,k] = input[0].split(" ").map(Number);
	
	let graph = Array.from({length:n}, ()=> []);
	
	for(let i = 1; i<input.length; ++i) {
		const [a,b] = input[i].split(" ").map(Number);
		
		graph[a-1].push(b-1);
		graph[b-1].push(a-1);
	}
	
	let start = 0;
	let visited = Array.from({length:n}, ()=> 0);
	let distances = Array.from({length:n}, ()=> Infinity);
	
	function search(start) {
		let q = [start];
		distances[start] = 0;
		visited[start] = 1;
		
		
		while(q.length) {
			const next = q.shift();
			for(let i = 0; i<graph[next].length; ++i){
				let val = graph[next][i];
				
				if(distances[next] > distances[val] + 1) {
					distances[next] = distances[val] + 1
				}
				
				if(!visited[val]) {
					q.push(val);
					visited[val] = 1;
				}
			}
		}
		
	}
	
	search(start);
	
	console.log(distances[n-1] <= k ? 'YES' : 'NO')
})