[JavaScript] 백준 2458번: 키 순서 (플로이드 워셜, DFS)

난이도 : 골드 4
알고리즘 유형 : 플로이드 워셜, DFS
문제 링크 : https://www.acmicpc.net/problem/2458

 

 

문제

1번부터 N번까지 번호가 붙여져 있는 학생들에 대하여 두 학생끼리 키를 비교한 결과의 일부가 주어져 있다. 단, N명의 학생들의 키는 모두 다르다고 가정한다. 

학생들의 키를 비교한 결과가 주어질 때, 자신의 키가 몇 번째인지 알 수 있는 학생들이 모두 몇 명인지 계산하여 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 학생들의 수 N (2 ≤ N ≤ 500)과 두 학생 키를 비교한 횟수 M (0 ≤ M ≤ N(N-1)/2)이 주어진다.

다음 M개의 각 줄에는 두 학생의 키를 비교한 결과를 나타내는 N보다 작거나 같은 서로 다른 양의 정수 a와 b가 주어진다. 이는 번호가 a인 학생이 번호가 b인 학생보다 키가 작은 것을 의미한다.

출력

자신이 키가 몇 번째인지 알 수 있는 학생이 모두 몇 명인지를 출력한다.

 

 

풀이 과정

• 메인 생각 : 자신의 키가 몇 번째인지 어떻게 알 수 있을까?
                      => 자신보다 작은 사람의 수 + 자신보다 큰 사람의 수 == N - 1

문제는 플로이드 워셜과 DFS를 활용하여 2가지 방안으로 풀었다.

 

 

< 플로이드 워셜 >

• table[ i ][ j ] === true  이면  i는 j보다 작다.
• table[ i ][ j ] === false 이면  j는 i보다 작은지 모른다.
• table[ j ][ i ] === true  이면  i는 j보다 크다.
• table[ j ][ i ] === false 이면  i는 j보다 큰지 모른다.

1. 입력 정리.
   • 최단 경로 테이블 초기화    // table[N][N]
   • 최단 경로 테이블 갱신       // 입력 a b에 대해 table[a][b] = true
2. 플로이드 워셜 알고리즘 실행.
   • 중간 노드 m을 통해 i가 j보다 작은지 확인   // table[i][m] && table[m][j]
3. 정답 구하기.
   • 자신보다 큰 사람의 수 + 자신보다 작은 사람의 수 == N - 1 인 사람의 수 

코드

const filePath = process.platform === 'linux' ? '/dev/stdin' : 'BACKJOON_002458.txt';
const input = require('fs').readFileSync(filePath).toString().trim().split(/\r?\n/);

const [N, M] = input.shift().split(' ').map(Number);

const table = Array.from(new Array(N), () => new Array(N).fill(false));

input.forEach((data) => {
  const [a, b] = data.split(' ').map(Number);
  table[a-1][b-1] = true;
})

for(let m=0; m<N; m++)
for(let i=0; i<N; i++)
for(let j=0; j<N; j++)
  if(table[i][m] && table[m][j]) table[i][j] = true;

let answer = 0;
let count = 0;

for(let i=0; i<N; i++){
  for(let j=0; j<N; j++){
    if(table[i][j] || table[j][i]) count++;
  }
  if(count === N-1) answer++;
  count = 0;
}

console.log(answer);

 

 

 

< DFS >

1. 입력 정리.
   • tall     : 자신보다 큰 사람을 자신의 index에 저장
   • short : 자신보다 작은 사람을 자신의 index에 저장 
2. DFS를 통해 정답 구하기.
   
   • dfs를 통해 자신보다 큰 사람들의 번호 측정
   • dfs를 통해 자신보다 작은 사람들의 번호 측정
   • 자신보다 큰 사람의 수와 자신보다 작은 사람의 수가 N-1인지 확인

코드

const filePath = process.platform === 'linux' ? '/dev/stdin' : 'BACKJOON_002458.txt';
const input = require('fs').readFileSync(filePath).toString().trim().split(/\r?\n/);

const [N, M] = input.shift().split(' ').map(Number);

const tall = Array.from({length: N}, () => []);
const short = Array.from({length: N}, () => []);

input.forEach((data) => {
  const [s, t] = data.split(' ').map(Number);
  tall[s-1].push(t-1);
  short[t-1].push(s-1);
})

let answer = 0;
let count = 0;

for(let i=0; i<N; i++){
  const visited_tall = Array.from({length: N}, () => false);
  const visited_short = Array.from({length: N}, () => false);
  dfs(i, visited_tall, tall);
  dfs(i, visited_short, short);
  
  for(let i=0; i<N; i++){
    if(visited_tall[i] || visited_short[i]) count++;
  }
  if(count === N-1) answer++;
  count=0;
}

console.log(answer);

function dfs(idx, visited, edge){
  for(const nextI of edge[idx]){
    if( visited[nextI] ) continue;
    visited[nextI] = true;
    dfs(nextI, visited, edge);
  }
}

 

 

회고

자신의 순서를 정확히 아는 사람의 수를 찾는 방법을 생각하는데 시간이 든 문제인것 같다. 처음에는 graph에 초점을 두어 노드들의 갈래가 모이는 지점을 찾아야한다고 생각했다. 하지만 각각의 갈래에 초점을 두는 것이 아닌 전체 child, parent에 초점을 두었어야 했던 문제라고 생각된다.