구름톤 챌린지 15일차 일기

문제 13. 발전기 (2)

let input, N, K;
const village = [];
rl.on('close', () => {
	const dir = [[1, 0], [-1, 0], [0, 1], [0, -1]]
	const groups = Array(33).fill(0);
	const memo = Array.from(Array(Number(N)), () => Array(Number(N)).fill(0));
	
	const BFS = (i, j) => {
		let cnt = 1;
		const queue = [[i, j]];
		while (queue.length) {
			const queuePop = queue.shift();
			const queueI = queuePop[0]
			const queueJ = queuePop[1]
			memo[queueI][queueJ] = 1
			dir.map((d) => {
				const nextI = queueI + d[0]
				const nextJ = queueJ + d[1]
				if (nextI < 0 || nextJ < 0 || nextI >= N || nextJ >= N || memo[nextI][nextJ] === 1) return;
				if (village[queueI][queueJ] === village[nextI][nextJ]) {
					cnt++;
					queue.push([nextI, nextJ])
					memo[nextI][nextJ] = 1
				}
			})
		}
		if (cnt >= K) {
			groups[village[i][j]] += 1
		}
	}
	
	for (let i=0; i<N; i++) {
		for (let j=0; j<N; j++) {
			if (memo[i][j] === 1) continue;
			BFS(i, j);
			memo[i][j] = 1
		}
	}
	
	let maxValue = 0;
	let result = 0;
	groups.map((el, idx) => {
		if (el >= maxValue) {
			maxValue = el;
			result = idx;
		}
	})
				
	console.log(result)
})

BFS로 탐색한 후에

단지의 갯수가 k보다 큰지,

가장 많은 단지를 가진 곳은 어딘지,

조건을 추가 탐색한 후 result를 출력했다.

 

배열을 사용해서 푸는 게 익숙해서 항상 그렇게 풀었는데 일상이가 객체로 리팩토링 해보라고 해서 같이 해봤다.

let input, N, K;
const village = [];
const memo = [];
const dir = [[1, 0], [-1, 0], [0, 1], [0, -1]];
const groups = Array(33).fill(0);

const BFS = (i, j, curNumber) => {
	let cnt = 1;
	const queue = [{r: i, c: j}];
	
	while (queue.length) {
		const {r, c} = queue.shift();

		dir.forEach((d) => {
			const nextI = r + d[0]
			const nextJ = c + d[1]
			if (nextI < 0 || nextJ < 0 || nextI >= N || nextJ >= N || memo[nextI][nextJ] === 1 || curNumber !== village[nextI][nextJ]) return;
			cnt++;
			queue.push({r:nextI, c:nextJ});
			memo[nextI][nextJ] = 1;
		});
	}
	if (cnt >= K) {
		groups[village[i][j]] += 1
	}
}

rl.on('close', () => {
	for (let i=0; i<N; i++) {
		for (let j=0; j<N; j++) {
			if (memo[i][j] === 1) continue;
			memo[i][j] = 1;
			const cur = village[i][j];
			BFS(i, j, cur);
		}
	}
	
	let maxValue = 0;
	let result = 0;
	groups.forEach((el, idx) => {
		if (el < maxValue) return;
		maxValue = el;
		result = idx;
	})

	console.log(result)
})

오.. 코드가 깔끔해짐 ..

 

 

문제 14. 작은 노드

const node = [];
rl.on('close', () => {
	const [n, m, k] = input[0].split(" ").map(Number)
	const node = input.slice(1).map((el) => el.split(" ").map(Number))
	
	const map = {};
	node.forEach(([i, j]) => {
		!map[i] ? map[i] = [j] : map[i].push(j)
		!map[j] ? map[j] = [i] : map[j].push(i)
	})
	
	const memo = [];
	let cur = k;
	memo.push(cur);
	
	while (true) {
		if (!map[cur]) break;
		let next = map[cur].filter(el => !memo.includes(el)).sort((a, b) => a - b)[0];
		if (!next) break;
		memo.push(next);
		cur = next
	}
	
	console.log(memo.length, cur)
})

양방향 그래프 기본 문제인데.. 난 그래프 문제 싫어 하는 편(ㅠ)

심지어 처음에 문제도 제대로 안 읽었는지 단방향 으로 풀었다가 틀리고

sort 제대로 안 줘서 또 틀리고

ㅋㅋㅋㅋ

 

아무튼 map 객체에 해당 노드를 키로 해당 노드에서 갈 수 있는 노드들을 모두 넣었고

방문할 때 마다 memo 배열에 마지막 방문 노드 값을 넣어줘서

마지막에 memo.length로 방문한 노드 갯수와 현재 노드 값을 출력해줌!