백준 / 최단경로 - Floyd Warshall / 11403번 / 경로 찾기 / JS

문제

가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 경로가 있는지 없는지 구하는
프로그램을 작성하시오.

입력

첫째 줄에 정점의 개수 N (1 ≤ N ≤ 100)이 주어진다. 둘째 줄부터 N개 줄에는 그래프의 인접 행렬이 주어진다.
i번째 줄의 j번째 숫자가 1인 경우에는 i에서 j로 가는 간선이 존재한다는 뜻이고, 0인 경우는 없다는 뜻이다.
i번째 줄의 i번째 숫자는 항상 0이다.

출력

총 N개의 줄에 걸쳐서 문제의 정답을 인접행렬 형식으로 출력한다. 정점 i에서 j로 가는 경로가 있으면 i번째 줄의
j번째 숫자를 1로, 없으면 0으로 출력해야 한다.

예제 입력 1 

3
0 1 0
0 0 1
1 0 0

예제 출력 1

1 1 1
1 1 1
1 1 1

 

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

// shift는 처음값을 return 하고 삭제한다.
const N = +input.shift();

// 문자열로 되어있는 배열을 공백 기준으로 잘러서,
// 각각을 숫자로 만들어준다.
let arr = [];
input.map(item => {
  let tmp = item.split(' ').map(item => +item);
  arr.push(tmp);
});

// Floyd-Warshall Algorithm
function solution(N, matrix) {
  // k는 거쳐갈 중간노드를 나타낸다.
  for(let k=0; k<N; k++) {
    for(let i=0; i<N; i++) {
      for(let j=0; j<N; j++) {
        // k를 거쳐서 i부터 j까지 갈 수 있다면,
        if(matrix[i][k] && matrix[k][j]) {
          matrix[i][j] = 1;
        }
      }
    }
  }

  // 출력예시에 맞게 출력
  for(let i=0; i<N; i++) {
    console.log(matrix[i].join(' '));
  }
}

solution(N, arr);

---

최단 경로를 구하는 알고리즘인 Dijkstra Algorithm과 Floyd-Warshall Algorithm 중에서 후자를 사용하는 문제이다.

 

Floyd-Warshall Algorithm에 관한 정리글은 아래 ↓ 

2022.04.26 - [ALGORITHM/개념] - Floyd-Warshall Algorithm (최단경로)

Floyd-Warshall Algorithm (최단경로)