저울

문제

백준 10159번 - 저울

언어

JavaScript

순서도

자신에서 자신으로 가는 간선 비용 0 으로 초기화
그래프 정보를 이용해서 간선 비용 초기화
플로이드 워셜 알고리즘을 수행해서 모든 간선간의 최단 경로 구하기
모든 정점에 대해서 각 정점마다 연결되어 있지 않은 정점의 개수 세기

문제 풀이 step 1

무게가 서로 다른 N 개의 물건이 있습니다.
각 물건은 1 부터 N 까지 번호가 매겨져 있습니다.
우리는 일부 물건 쌍에 대해서 양팔 저울로 어떤 것이 무거운 것인지 측정한 결과표를 가지고 있습니다.
이 결과표로부터 직접 측정하지 않은 물건 쌍의 비교 결과를 알아낼 수도 있고 알아내지 못할 수도 있습니다.
예를 들어, 총 6 개의 물건이 있고, 다음 5 개의 비교 결과가 주어졌다고 가정하겠습니다. ([1]은 1 번 물건의 무게를 의미합니다.)
- [1] > [2], [2] > [3], [3] > [4], [5] > [4], [6] > [5]
- 우리는 [2] > [3], [3] > [4]로부터 [2] > [4]라는 것을 알 수 있습니다. 하지만, 물건 2와 물건 6을 비교하는 경우, 앞서의 결과만으로는 어느 것이 무거운지 알 수 없습니다.
- 이와 같이, 물건 2 는 물건 1, 3, 4 와의 비교 결과는 알 수 있지만, 물건 5, 6 과의 비교 결과는 알 수 없습니다.
- 물건 4 는 모든 물건과의 비교 결과를 알 수 있습니다.
비교 결과가 모순되는 입력은 없다고 가정합니다.
물건의 개수 n 과 일부 물건 쌍의 비교 결과가 주어졌을 때, 각 물건에 대해서 그 물건과의 비교 결과를 알 수 없는 물건의 개수를 구하는 문제입니다.

문제 풀이 step 2

본 문제는 플로이드 워셜 알고리즘을 적용하면 쉽게 풀 수 있습니다.
각 물건에 대해서 비교 결과를 알려면 그래프로 표현했을 때, 서로 연결되어 있어야 하겠죠??
이전 문제들에서도 알아봤듯이 플로이드 워셜 알고리즘은 각 정점간의 최단 경로뿐만 아니라, 각 정점간의 연결 정보도 얻을 수 있습니다.
- 백준 2458번 - 키 순서 풀이
따라서 플로이드 워셜 알고리즘을 이용해서 모든 물건 간의 최단 경로를 구합니다.
그리고 모든 정점에 대해서 각 정점별로 다른 정점과 연결되지 않은 정점의 개수를 세서 출력하면 됩니다.
- 정점이 다른 정점과 연결되었는지 안 되었는지는 그 정점에서 다른 정점으로 가는 최단 경로가 있는지, 다른 정점에서 그 정점으로 가는 최단 경로가 있는지를 검사함으로써 알 수 있습니다.
추가 설명은 주석으로 작성하겠습니다.

소스 코드

const input = require("fs")
	.readFileSync("/dev/stdin")
	.toString()
	.trim()
	.split("\n");

const INF = Math.floor(Number.MAX_SAFE_INTEGER / 2);

const solution = (input) => {
	const n = Number(input[0]);
	const m = Number(input[1]);

	const dist = Array.from(Array(n), () => Array(n).fill(INF));

	// 자신에서 자신으로 가는 경로 0 으로 초기화
	for (let i = 0; i < n; i++) {
		dist[i][i] = 0;
	}

	// 그래프 정보를 이용해서 각 간선 정보 입력
	for (let i = 2; i < m + 2; i++) {
		const [x, y] = input[i].split(" ").map(Number);

		dist[x - 1][y - 1] = 1;
	}

	// 플로이드 워셜 알고리즘 적용
	for (let k = 0; k < n; k++) {
		for (let i = 0; i < n; i++) {
			for (let j = 0; j < n; j++) {
				dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);
			}
		}
	}

	// 모든 정점에 대해서 각 정점별로 연결되어 있지 않은 정점의 개수 세기
	let res = "";
	for (let i = 0; i < n; i++) {
		let cnt = 0;

		for (let j = 0; j < n; j++) {
			if (dist[i][j] === INF && dist[j][i] === INF) cnt += 1;
		}

		res += `${cnt}\n`;
	}

	return res;
};

console.log(solution(input));