[JavaScript] 구름톤 챌린지 4주차 코딩테스트 : 연합 (다시 풀어야 함)

📌  문제

📌  입력

📌  출력 및 예제

---

📌  풀이

알아야 하는 것

• Array.from
• BFS

구할 것

• BFS로 구현한다.
• union-find 알고리즘으로 푼 분들이 많던데 이게 뭔지 알아봐야겠다.

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

rl.on('close', () => {
	const [island, bridge] = input.shift();
	let union = 1; // 연합 번호
	const graph = Array.from(Array(island+1), () => []); // 그래프
	const visited = Array(island+1).fill(0); // 연합 카운트 [0, 1, 0, 0, 0]
	const map = Array.from(Array(island+1), () => Array(island+1).fill(false)) // 연결된 다리 확인
	
	// 단방향 연결
	for (let [from, to] of input) {
		graph[from].push(to)
		map[from][to] = true;
	}
	
	let queue = [];

	for (let i = 1; i <= island; i++) {
		// 아직 연합이 없다면 탐색
		if (!visited[i]) {
			queue.push(i)
			
			while (queue.length) {
				const curNode = queue.shift();
				visited[curNode] = union;
				
				// graph 순회할 때 다음으로 연결된 것도 확인
				if (graph[curNode]) {
					for (let nextNode of graph[curNode]) {
						// curNode랑 이어진 NextNode가 있고 연결된 다리도 있고 방문하지도 않았을 때
						if (graph[nextNode] && map[nextNode][curNode] && !visited[nextNode]) {
							queue.push(nextNode)
						}
					}
				}
			}
			union++; // 쭉 이어지면 같은 숫자로 union
			
		}
	}
	console.log(union-1)
})