[Node.js] 구름 Level 3_ 단풍나무

문제

https://level.goorm.io/exam/167345/%EB%8B%A8%ED%92%8D%EB%82%98%EB%AC%B4/quiz/1

구름LEVEL

 

 

풀이

이 문제는 백준의 연구소 문제 시리즈에서 많이 풀었던 그래프 탐색 문제이다.

 

그래프 탐색을 할 때 큐를 이용해 탐색해야 하는 단풍이 다 열리지 않은 지역을 탐색했는데, 지역의 위치를 구하는데 조심해야 하는 부분은 아침 기준으로 구해야 하기에 while 문에서 계속해서 큐에 위치를 qush해주면 안된다.

 

위의 조건을 조심해서 풀면 잘 풀 수 있지만, 나는 한가지 경우의 수를 놓쳤다.

바로 모두 완벽하게 열린 경우인데, 즉 필드에 있는 모든 값이 0인 경우이다.

이 때는 검증 및 확산 동작을 하지 않고도 완료 조건에 충족하기에 0을 출력 해야한다.

 

코드

// Run by Node.js
const readline = require('readline');

(async () => {
	let rl = readline.createInterface({ input: process.stdin });
	let input = [];
	
	for await (const line of rl) {
		input.push(line);
		if(input.length === (+input[0] + 1)) rl.close();
	}
	
	const sol = (data) => {
		const n = +data.shift();
		let map = data.map(e => e.split(' ').map(Number));
		const dir = [[-1, 0], [1, 0], [0, -1], [0, 1]];
		let time = 0;
		
		while(true){
			const que = [];
			let mapleCnt = 0;
			// map에 직접 단풍이 모두 물들게 하면 아침 기준의 구역을 이용하라는 조건에 부합하지 않음.
			const temp = Array.from({length: n}, () => Array(n).fill(0));
			
			for(let i = 0; i < n; i++){
				for(let j = 0; j < n; j++){
					if(map[i][j] !== 0) {
						que.push([i, j]);
						mapleCnt += map[i][j];
					}
				}
			}
			
			if(mapleCnt <= 0) break;
			time++;
			
			while(que.length > 0){
				const [y, x] = que.shift();
				let cnt = 0;
				
				for(let d = 0; d < 4; d++){
					const nY = y + dir[d][0];
					const nX = x + dir[d][1];
					if(nY >= 0 && nX >= 0 && nY < n && nX < n && map[nY][nX] === 0) cnt++;
				}
				
				temp[y][x] = map[y][x] < cnt ? 0 : map[y][x] - cnt;
				mapleCnt -= (map[y][x] < cnt ? map[y][x] : cnt);
			}
			
			map = temp;
			
		}
		console.log(time)
	}
	sol(input);
	process.exit();
})();