키 순서

문제

언어

  • JavaScript

순서도

  1. 자신에서 자신으로 가는 간선 비용 0 으로 초기화
  2. 그래프 정보를 이용해서 간선 비용 초기화
  3. 플로이드 워셜 알고리즘을 수행해서 모든 간선간의 최단 경로 구하기
  4. 모든 정점들에 대해서 자신이 가진 모든 경로에서 시작점 혹은 도착점으로 연결되어 있는 정점의 개수 세기

문제 풀이 step 1

  • 1 번부터 N 번까지 번호가 붙여져 있는 학생들에 대하여 두 학생끼리 키를 비교한 결과의 일부가 주어져 있습니다.
  • 단, N 명의 학생들의 키는 모두 다르다고 가정합니다.
  • 예를 들어, 6 명의 학생들에 대하여 6 번 키를 비교하였고, 그 결과가 다음과 같다고 합니다.
    • 1번 학생의 키 < 5번 학생의 키
    • 3번 학생의 키 < 4번 학생의 키
    • 5번 학생의 키 < 4번 학생의 키
    • 4번 학생의 키 < 2번 학생의 키
    • 4번 학생의 키 < 6번 학생의 키
    • 5번 학생의 키 < 2번 학생의 키
  • 이 비교 결과로부터 모든 학생 중에서 키가 가장 작은 학생부터 자신이 몇 번째인지 알 수 있는 학생들도 있고, 그렇지 못한 학생들도 있다는 사실을 아래의 그림을 통해서 확인할 수 있습니다. 백준 2458번 - 키 순서 문제 사진
  • 1 번은 5 번보다 키가 작고, 5 번은 4 번보다 작기 때문에, 1 번은 4 번보다 작게 됩니다. 그러면 1 번, 3 번, 5 번은 모두 4 번보다 작게 됩니다.
  • 또한 4 번은 2 번과 6 번보다 작기 때문에, 4 번 학생은 자기보다 작은 학생이 3 명이 있고, 자기보다 큰 학생이 2 명이 있게 되어 자신의 키가 몇 번째인지 정확히 알 수 있습니다. 그러나 4 번을 제외한 학생들은 자신의 키가 몇 번째인지 알 수 없습니다.
  • 학생들의 키를 비교한 결과가 주어질 때, 자신의 키가 몇 번째인지 알 수 있는 학생들이 모두 몇 명인지 계산하는 문제입니다.

문제 풀이 step 2

  • 본 문제는 플로이드 워셜 알고리즘을 적용하면 쉽게 풀 수 있습니다.
  • 플로이드 워셜 알고리즘은 모든 정점간의 최단 경로를 구하는 데에 사용하지만, 이에 추가로 모든 정점간의 연결 정보를 파악하는 데에도 사용될 수 있습니다.
  • 본 문제에서 자신의 키가 몇 번째인지 알 수 있으려면, 그 학생은 모든 학생들과 연결되어 있어야 합니다.
    • 여기서 모두와 연결되어 있다는 얘기는 그래프에서 설명을 하자면, 자신을 제외한 모든 정점들과의 관계에서 시작점 혹은 도착점으로 연결되어 있어야 한다는 뜻입니다.
    • 위의 문제에서 제공해준 예시를 참고해서 설명하자면,
      • 4 번 정점은 1 번, 3 번, 5 번 정점으로부터 도착점으로 연결되어 있습니다.
      • 그리고 2 번, 6 번 정점의 시작점으로 연결되어 있습니다.
      • 이렇게 모두와 연결되어 있기 때문에 자신의 키가 몇 번째인지 알 수 있는 것입니다.
  • 따라서 플로이드 워셜 알고리즘을 적용해서 모든 정점들의 연결 정보를 파악합니다.
  • 그리고 각 정점이 자신을 제외한 다른 정점들과 시작점 혹은 도착점으로 연결되어 있는지 검사하고, 그러한 조건을 만족하는 정점들의 개수를 세서 출력하면 정답입니다.
  • 추가 설명은 주석으로 작성하겠습니다.

후기

  • 플로이드 워셜 알고리즘을 이용하면 각 정점간의 최단 경로뿐만 아니라, 각 정점들의 연결 정보도 파악할 수 있다는 것을 깨달을 수 있었습니다.

소스 코드

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

const solution = (input) => {
	const INF = Number.MAX_SAFE_INTEGER;

	const [n, m] = input[0].split(" ").map(Number);

	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 = 1; i < m + 1; i++) {
		const [fx, fy] = input[i].split(" ").map(Number);

		dist[fx - 1][fy - 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 cnt = 0;
	for (let i = 0; i < n; i++) {
		let flag = true;

		// 다른 정점들과 시작점 혹은 도착점으로 연결되어 있는지 검사
		for (let j = 0; j < n; j++) {
			if (dist[i][j] !== INF || dist[j][i] !== INF) continue;

			flag = false;
		}

		if (flag) cnt += 1;
	}

	return cnt;
};

console.log(solution(input));