[Javascript][BOJ] 2458 키 순서

www.acmicpc.net/problem/2458

2458번: 키 순서

 

핵심아이디어

문제에서 요구한 구현사항을 그대로 구현하기만 하면된다.

각 정점에 대해, ~보다 작은 수/~보다 큰 수를 구한뒤 더 했을때 n-1개가 되면 자신의 위치를 정확히 알고 있는 점을 이용한다.

~보다 작은 수/~보다 큰 수는 어떻게 구하는가?

각 정점간의 relation을 dfs의 edge처럼 사용하여 탐색하며 카운팅해주면 된다.

끝이다.

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

const solution = function (input) {
	const [n, m] = input
		.shift()
		.split(' ')
		.map((e) => parseInt(e));

	const upRelations = Array.from({ length: n + 1 }, () => []); // 보다 큰수를 찾을 때 사용하는 relation
	const downRelations = Array.from({ length: n + 1 }, () => []); // 보다 작은수를 찾을 때 사용하는 relation

	const upCnt = Array.from({ length: n + 1 }, () => 0); // 내 위에 몇명이 있는가?
	const downCnt = Array.from({ length: n + 1 }, () => 0); // 내 아래에 몇명이 있는가?

	let upVisited = Array.from({ length: n + 1 }, () => 0); // // 보다 큰수를 찾을 때 사용하는 visited
	let downVisited = Array.from({ length: n + 1 }, () => 0); // 보다 작은수를 찾을 때 사용하는 visited

	for (const row of input) {
		const [a, b] = row.split(' ').map((e) => parseInt(e));
		upRelations[a].push(b);
		downRelations[b].push(a);
	}

	const cntUp = (cnt, num) => {
		upVisited[num] = 1;
		for (const dest of upRelations[num]) {
			if (upVisited[dest] === 1) continue;
			cnt++;
			cnt = cntUp(cnt, dest);
		}
		return cnt;
	};
	const cntDown = (cnt, num) => {
		downVisited[num] = 1;
		for (const dest of downRelations[num]) {
			if (downVisited[dest] === 1) continue;
			cnt++;
			cnt = cntDown(cnt, dest);
		}
		return cnt;
	};

	let ans = 0;

	for (let i = 1; i < n + 1; i++) {
		upVisited = Array.from({ length: n + 1 }, () => 0);
		downVisited = Array.from({ length: n + 1 }, () => 0);
		upCnt[i] = cntUp(
			0,
			i,
			Array.from({ length: n + 1 }, () => 0)
		);
		downCnt[i] = cntDown(
			0,
			i,
			Array.from({ length: n + 1 }, () => 0)
		);
		if (upCnt[i] + downCnt[i] === n - 1) ans++;
	}
	// console.log(upCnt);
	// console.log(downCnt);
	console.log(ans);
};

const input = [];
rl.on('line', function (line) {
	input.push(line);
}).on('close', function () {
	solution(input);
	process.exit();
});