[프로그래머스/그래프, 플로이드] lv3. 순위 (JavaScript)

다른 모든 노드와 연결된 노드의 개수 찾기

왜 이 문제가 그래프 문제인지 이해를 못하고 해메다가
결국 다른 분들 블로그를 참조해 해결했다.

플로이드 와샬 알고리즘 활용 풀이

정확하게 순위를 매길 수 있는 선수의 의미

• 다른 모든 노드와 그래프로 연결되어 있는 경우
• 플로이드 와샬을 활용한 풀이가 가장 출제의도에 잘 맞는 풀이인 것 같다.

참고: 연성님 블로그

/**
 * @param {number} n 선수의 수, 1~100
 * @param {number[][]} results 경기결과, [a, b] === a가 b를 이김
 * @returns {number} 정확하게 순위를 매길 수 있는 선수의 수
 */
const solution = (n, results) => {
	// 각 결과에 대해 2차원 배열에 표기
	const graph = Array.from({ length: n + 1 }, () => Array(n + 1).fill(false));
	results.map((val) => {
		const [win, lose] = val;
		graph[win][lose] = 1;
		graph[lose][win] = -1;
		graph[win][win] = 0;
		graph[lose][lose] = 0;
	});

	// Python의 range를 대체하여 좀더 간편하게 활용
	const rangeN = [...Array(n).keys()].map((e) => e + 1);

	// 플로이드 와샬 알고리즘 적용
	for (const mid of rangeN) {
		for (const a of rangeN) {
			for (const b of rangeN) {
				// a가 mid를 이기고, mid가 b를 이기면 a가 b를 이김
				if (graph[a][mid] === 1 && graph[mid][b] === 1) graph[a][b] = 1;
				// a가 mid에게 지고, mid가 b에게 지면 a가 b에게 짐
				if (graph[a][mid] === -1 && graph[mid][b] === -1)
					graph[a][b] = -1;
			}
		}
	}

	// 경기결과를 추측할 수 없는 경우는 false로 그대로 남아있음
	// 각 선수에 대해 false가 전혀 없는 경우만 ans + 1
	let ans = 0;
	for (const self of rangeN) {
		let hasFalse = false;
		for (const other of rangeN) {
			if (graph[self][other] === false) {
				hasFalse = true;
				break;
			}
		}
		ans += hasFalse ? 0 : 1;
	}

	return ans;
};

문제의 조건을 좀더 활용한(?) 풀이

모든 선수와의 대결기록을 유추할 수 있는 경우들을 찾는 문제이기 때문에,
O(V^3)의 플로이드 와샬까지 사용할 필요없이
승리한 경우의 수와 패배한 경우의 수를 구해서 풀이

이때 wins/losers를 업데이트하는 과정에서,
index 순서대로만 하는데도 전체가 잘 업데이트 될 수 있다는 게
아직 확실히는 모르겠다..

아래 테스트 결과처럼, 시간 효율성, 공간 효율성 모두 전반적으로 향상되었다.

참고: Doni’s Dev-note님 블로그

const solution = (n, results) => {
	const rangeN = [...Array(n).keys()].map((e) => e + 1);
	// key: winner, value : Set([losers])
	const wins = {};
	// key: loser, value : Set([winners])
	const loses = {};
	rangeN.map((key) => {
		wins[key] = new Set([]);
		loses[key] = new Set([]);
	});

	// 승패 결과 저장
	results.map((val) => {
		const [winner, loser] = val;
		wins[winner].add(loser);
		loses[loser].add(winner);
	});

	rangeN.map((i) => {
		// i 선수를 이긴 선수(losers[i])는 i 선수에게 패한 선수들(wins[i])도 이김
		for (const winner of [...loses[i]]) {
			if (!wins[winner]) continue;
			for (const loser of wins[i]) {
				wins[winner].add(loser);
			}
		}
		// i 선수에게 패한 선수는 i선수를 이긴 선수들에게도 패함
		for (const loser of [...wins[i]]) {
			if (!loses[loser]) continue;
			for (const winner of loses[i]) {
				loses[loser].add(winner);
			}
		}
	});

	return rangeN.reduce(
		(ans, i) => (wins[i].size + loses[i].size === n - 1 ? ans + 1 : ans),
		0
	);
};