[JS][백준]1613_역사

문제 번호

1613번: 역사

 

 

알고리즘 분류

• 그래프 이론
• 플로이드–와샬

 

문제 풀이

 Flody Warshall

24. 플로이드 와샬(Floyd Warshall) 알고리즘

 

 플로이드 와샬 알고리즘을 처음 써봤다. 뭔지 모를때는 뭔소린가 싶었는데 위의 블로그의 동영상 한번 보고나니까 이해됐다.

 

 플로이드은 대략 'i에서 k를 거쳐서 j로 간다' i -> k -> j 이므로 해당문제에 적용시켜보면 'i가 k보다 선행사건이고 k가 j보다 선행사건 이라면 i는 j보다 선행사건이다.' 로 적용시킬 수 있다.

 

 그래서 문제에서 주어진 선행사건들을 그래프로 옮긴다. 그래프의 초기값은 0(연결되어 있지않음, 즉 선후 관계를 알 수 없음)으로 하고 그래프를 작성한다.

let ans = new Array(N + 1).fill(null).map(x => new Array(N + 1).fill(0));

for (let i = 1; i <= N; i++) {  
  for (let j = 1; j <= N; j++) {
    if (i === j) 
      ans[i][j] = 0;        
  }
}

for(let i=0; i<K; i++){
  let AB = input.shift().split(' ').map(x=>Number(x));
  let A = AB[0];
  let B = AB[1];
  ans[A][B] = -1;
  ans[B][A] = 1;
}

 

이제 플로이드 와샬알고리즘을 사용해서 배열을 업데이트 시키면된다. 

'i가 k보다 선행사건이고 k가 j보다 선행사건 이라면 i는 j보다 선행사건이다.' 이므로 'i가 k보다 후행사건이고 k가 j보다 후행사건 이라면 i는 j보다 후행사건이다.' 도 된다.

function Flody() {
  // k를 거쳐간다.
  for (let k = 1; k <= N; k++) {
    // i에서 출발한다.
    for (let i = 1; i <= N; i++) {
      // j로 간다.
      for (let j = 1; j <= N; j++) {
        if(ans[i][k] === 1 && ans[k][j] === 1)
          ans[i][j] = 1;
        else if(ans[i][k] === -1 && ans[k][j] === -1)
          ans[i][j] = -1;
      }
    }
  }
}

 

전체코드

const fs = require('fs').readFileSync('역사/input.txt');
const input = fs.toString().trim().split('\n');
const NK = input.shift().split(' ');
const N = Number(NK.shift());
const K = Number(NK.shift());
let ans = new Array(N + 1).fill(null).map(x => new Array(N + 1).fill(0));

for (let i = 1; i <= N; i++) {  
  for (let j = 1; j <= N; j++) {
    if (i === j) 
      ans[i][j] = 0;        
  }
}

for(let i=0; i<K; i++){
  let AB = input.shift().split(' ').map(x=>Number(x));
  let A = AB[0];
  let B = AB[1];
  ans[A][B] = -1;
  ans[B][A] = 1;
}
const S = Number(input.shift());

function Flody() {
  // k를 거쳐간다.
  for (let k = 1; k <= N; k++) {
    // i에서 출발한다.
    for (let i = 1; i <= N; i++) {
      // j로 간다.
      for (let j = 1; j <= N; j++) {
        if(ans[i][k] === 1 && ans[k][j] === 1)
          ans[i][j] = 1;
        else if(ans[i][k] === -1 && ans[k][j] === -1)
          ans[i][j] = -1;
      }
    }
  }
}

Flody();
let answer = ''
for(let i=0; i<S; i++){
  let FS = input.shift().split(' ').map(x=>Number(x));
  let F = FS[0];
  let S = FS[1];
  
  answer += ans[F][S] + '\n'
}

console.log(answer);

 

 

특이사항

테스트 케이스 마다 정답을 출력하면 시간초과에 걸린다.

한번에 출력해야한다.