구름톤 챌린지 남은 문제들 푼 일기 (JavaScript)

 

구름톤 챌린지가 끝나고, 구름톤 오프라인 행사에도 참여 했었다.

오 그게 벌써 .. 2달 전 ?!

 

어쨌든, 바쁜 일들 지나고 시간 날 때 그래프 문제 중 못풀었던 문제들을 몰아서 마저 풀었었다.

그래프 문제들을 풀다 보니 내가 생각했던 것보다 그래프도 별 것 없잖아? 라고 생각을 조금 했는데

아마 기초적인 그래프 문제들을 풀어서 그런 것 같긴 하지만

그래프 문제라고 하면 좀 꺼려지고 풀기 싫고 못 풀 것 같고 그런 편견을 살짝 내려놓은 계기가 되었다.

 

---

문제 18. 중첩 점

구름LEVEL

const readline = require('readline');
let rl = readline.createInterface({
	input: process.stdin,
	output: process.stdout,
});
const input  = [];
rl.on('line', (line) => {
	input.push(line);
});

rl.on('close', () => {
	const [n, m] = input[0].split(" ").map(Number)
	const lines = input.slice(1,).map((el) => el.split(" ").map((el, idx) => {
		if (idx < 2) return Number(el)-1
		return el
	}))
	
	const arrayX = Array.from(Array(n), () => Array(n).fill(0));
	const arrayY = Array.from(Array(n), () => Array(n).fill(0));
	let result = 0;
	
	lines.forEach(line => {
		let [y, x, d] = line
		
		if (d === "L") {
			while (x >= 0) {
				arrayX[y][x] = (arrayX[y][x] || 0) + 1
				x--
			}
		} else if (d === "R") {
			while (x < n) {
				arrayX[y][x] = (arrayX[y][x] || 0) + 1
				x++
			}
		} else if (d === "U") {
			while (y >= 0) {
				arrayY[y][x] = (arrayY[y][x] || 0) + 1
				y--
			}
		} else if (d === "D") {
			while (y < n) {
				arrayY[y][x] = (arrayY[y][x] || 0) + 1
				y++
			}
		}
	})
	
	for (let i=0; i<n; i++) {
			for (let j=0; j<n; j++) {
				if (arrayY[i][j] && arrayX[i][j]) {
					result += arrayX[i][j] * arrayY[i][j]	
				}
			}
		}
	
	console.log(result)
})

x선과 y선을 긋는 arrayX, arrayY라는 2차원 배열을 각각 만들고,

input으로 받는 입력을 lines에 담고, lines를 순회하며

시작점과 방향에 따라 선이 그어지는 영역을 찾고 배열 좌표 값에 +1씩하여 표시해준다.

그리고 마지막에 두 배열의 같은 좌표의 값을 서로 곱하여 중첩 점의 개수를 세었다.

(선이 그어져있는 수만큼 곱할 때 어느 한쪽이라도 0이면 중첩이 없는 것이므로)

 

---

문제 19. 대체 경로

구름LEVEL

const readline = require('readline');
let rl = readline.createInterface({
	input: process.stdin,
	output: process.stdout,
});
const input = [];
rl.on('line', (line) => {
	input.push(line);
});

rl.on('close', () => {
	const [n, m, s, e] = input[0].split(" ").map(Number);
	const nodes = input.slice(1,);
	const map = {};
	nodes.forEach((item) => {
		const [start, end] = item.split(" ").map(Number);
		map[start] = [...(map[start] || []), end]
		map[end] = [...(map[end] || []), start]
	})
	
	for (let day=1; day<=n; day++) {
		let dayCnt = 0;
		let flag = false;
		const visited = Array(n+1).fill(0);
		
		if (day === s || day === e) {
			console.log(-1)
			continue;
		}
		
		const q = [s];
		while (q.length) {
			dayCnt += 1;
			
			let fixedLength = q.length;
			for (let k=0; k<fixedLength; k++) {
				const cur = q.shift();
				visited[cur] = 1;
				
				map[cur].forEach((item) => {
					if (item === e) {
						flag = true;
						dayCnt += 1;
					} else if (item !== day && visited[item] === 0) {
						q.push(item);
					}
				})
				if (flag) break;
			}
			if (flag) break;
		}
		
		if (!flag) {
			dayCnt = -1;
		}
		console.log(dayCnt)
	}
})

 

체크하지 않아도 되는 day는 빠져나갈 수 있도록 종료조건을 미리 정해주고 

visited에 체크 되지 않은 탐색할 경로를 queue에 넣어 BFS형식으로 경로를 탐색

 

---

문제 20. 연결 요소 제거하기

구름LEVEL

const readline = require('readline');
let rl = readline.createInterface({
	input: process.stdin,
	output: process.stdout,
});
const input = [];
rl.on('line', (line) => {
	input.push(line);
});

rl.on('close', () => {
	const [n, k, q] = input[0].split(" ").map(Number);
	const array = input.slice(1, n+1).map((item) => item.split(""));
	const words = input.slice(n+1,).map((item) => item.split(" ").map((item, idx) => {
		if (idx < 2) {
			return Number(item)-1
		} else {
			return item
		}
	}));
	const dir = [[0, 1], [1, 0], [0, -1], [-1, 0]];
	
	words.forEach(([y, x, c]) => {
		array[y][x] = c;
		const visited = Array(n).fill(0).map((item) => Array(n).fill(0));
		const memo = [[y, x]];
		let cnt = 1;
		
		const queue = [[y, x]];
		visited[y][x] = 1;
		
		while (queue.length) {
			const [y, x] = queue.shift();
			dir.forEach(([dy, dx]) => {
				dy += y
				dx += x
				if (dy < n && dy >= 0 && dx < n && dx >= 0 && !visited[dy][dx]) {
					if (array[dy][dx] === c) {
						queue.push([dy, dx]);
						memo.push([dy, dx]);
						visited[dy][dx] = 1;
						cnt++;
					}
				}
			})
		}
		
		if (cnt >= k) {
			memo.forEach(([y, x]) => {
				array[y][x] = ".";
			})
		}
	})
	console.log(array.map(item => item.join("")).join("\n"))
})

위와 동일하게 queue를 활용한 BFS 풀이인 것은 동일하지만

연결 요소를 지울 때마다 배열을 새로 업데이트 한 후에 다음 연결 요소를 지운다는 것을 제대로 이해하고 풀어야 한다.

원본 배열을 수정하는 것이 보통 바람직하지 않다고 일반적으로 알고 있지만.. 이 문제는 그렇지 않으면 풀 수 없을 것 같다 ..??

ㅎㅎ 그래서 처음에 잘못 풀었다가 다시 고쳐 풀었떤..

 

---

 

구름톤 챌린지가 끝난 지도, 이 문제들을 다시 푼 지도 꽤 오래 되었더니

문제를 다시 읽고 내 코드를 이해하는 데 또 조금의 시간을 들였다.

역시 할일이 있으면 미리미리 해버리는 게 제일 좋은데 . . 알면서도 쉽게 미루게 되는 것 같다 😂