[Node.js] 구름톤 챌린지 3주 Day2 풀이 (발전기)

문제

• 한 변의 길이가 N인 정사각형 마을 M이 있다.
• r번째 행, c번째 열에 하당하는 칸 Mrc에는 0과 1이 적혀있다.
• 0이면 아무것도 없는 칸이고 1이면 집이 있는 칸이다.
• 마을에 있는 집에 전력을 공급하기 위해선 그 집에 발전기를 설치하거나, 상하좌우로 인접한 집 중 하나가 전력을 공급받고 있어야 한다.
• 마을 M의 모든 집에 전력을 공급할 경우, 발전기의 최소 갯수를 구하여라

 

코드

const readline = require('readline');
let rl = readline.createInterface({
	input: process.stdin,
	output: process.stdout,
});

let input = [];

rl.on('line', (line) => {
	input.push(line.trim())
}).on('close', () => {
	const N = parseInt(input[0])
	const matrix = input.slice(1).map((str) => str.split(" ").map(Number))
	const visited = Array.from(Array(N), () => Array(N).fill(false))
	const DIR_ARR = [
		[-1, 0],
		[0, -1],
		[0, 1],
		[1, 0]
	]
	
	let count = 0
  // 최초로 발견한 방문하지 않은 집에는 발전기를 설치해줘야 함
	// 집이 상하좌우로 연결되어 있다면 집단 내 랜덤한 하나의 집에만 발전기가 설치되면 됨.
	for (let i = 0; i < N; i++) {
		for (let j = 0; j < N; j++) {
			if (matrix[i][j] === 1 && !visited[i][j]) {
				// 최초로 발견한 집에는 발전기를 설치
				count++
				const stack = []
				stack.push([i, j])
				
				// 이후에 발견한 발전기와 연결된 집들은 방문만 체크
				while (stack.length > 0) {
					const [y, x] = stack.pop()
					visited[y][x] = true
					
					for (const [dy, dx] of DIR_ARR) {
						const nextY = y + dy
						const nextX = x + dx
						if (nextY >= 0 && nextY < N && nextX >= 0 && nextY < N) {
							if (matrix[nextY][nextX] === 1 && !visited[nextY][nextX]) {
								stack.push([nextY, nextX])
							}
						}
					}
				}
				// while문이 끝나고 다시 for문을 돌때는 이미 방문한 곳은 지나치게 됨
				// 따라서 연결되지 않은 집의 군집에 발전기를 하나씩 설치할 수 있음
			}
		}
	}
	
	console.log(count)
})

 

BFS

모든 집에 전기 공급을 해야하고, 상하좌우로 연결되어 있는 집들에 대해서는 하나의 집만 전기가 들어와도 된다.

체라 소서가 생각난다.

탐색된 첫번째 집에 발전기를 설치해두고, 그 집에 상하좌우로 연결된 모든 집들은 방문처리를 한다.

이후 for문을 통해 연결되지 않은 별도의 집들을 계속 탐색하여 발전기를 세워준다.