[JavaScript] 백준 11403번: 경로 찾기 (플로이드 워셜)

1년 4개월만의 블로그 복귀입니다! 99클럽 코테 스터디를 진행하면서 앞으로 TIL을 작성할 겁니다.

 

난이도 : 실버 1
알고리즘 유형 : 플로이드 워셜, 최단 경로
문제 링크 : https://www.acmicpc.net/problem/11403

 

 

문제

가중치 없는 방향 그래프 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으로 출력해야 한다.

 

 

알고리즘 분류

  그래프 이론    |    그래프 탐색    |    최단 경로   |    플로이드-워셜

 

처음에 알고리즘 분류를 보고 '어 플로이드 워셜? 어떤 알고리즘인지 기록했던 것 같은데' 하고 오랜만에 블로그를 방문했었다.

하지만.. 작성자인 나조차 알아보기 힘든 설명.. 뭐라는거지..ㅠㅠ

그래서 이번에는 좀 자세하기 작성해볼까 한다!

 

문제 풀이를 보고 싶으면 아래로 내려가주세용

 

플로이드 워셜 ( Floyd Warshall )

• 모든 노드 간의 최단 경로를 탐색하는 알고리즘 중 하나이다.
• 음의 가중치가 있는 그래프에서도 최단 경로를 구할 수 있다.
• $ O(N^3) $의 시간 복잡도를 가진다. (N : 노드의 개수)

알고리즘의 과정

1. 노드의 갯수 $ N^2 $ 만큼의 2차원 인접 행렬을 구성하여 최단 경로 테이블을 초기화한다.    // graph[N][N]
2. 1번 노드 부터 N번 노드까지 한 번씩 중간자 노드로 설정한다.  // for(let m = 0; m < N; i++)  
3. 중간자 노드 m을 거쳐서 가는 거리를 비교하여 최단 거리 테이블을 업데이트한다.
                //  for (let s = 0; s < N; s++) {
                //      for ( let e = 0; e < N; e++) {
                //          graph[s][e] = min( graph[s][e], graph[s][m] + graph[m][e]);
                //      }
                //  }
   
4. 3번 과정을 2번에 나온 것 처럼 N번 반복하면 이제 모든 노드에 대한 최단 경로 테이블을 얻을 수 있다.

function floyd_warshall(graph) {
  cosnt N = graph.length;

  for (let m=0; m<N; m++) // 중간자 노드 선택
  for (let s=0; s<N; s++) // 시작 노드 선택
  for (let e=0; e<N; e++) // 끝 노드 선택
    graph[s][e] = Math.min(graph[s][e], graph[s][m] + graph[m][e]);
	
  return graph;
}

 

설명이 예전 것과 달라진 부분이 있겠죠..? ㅎㅎ

 

 

백준 11403 경로 찾기

플로이드 워셜 알고리즘은 모든 노드의 최단 경로를 찾지만 이번 문제에서는 거리가 아닌 경로가 있는지만 확인하면 된다!

그래서 더 작은 값을 구하는 것이 아닌 중간자 노드를 통해서 연결이 되는지만 확인하도록 코드를 수정하였다.

const filePath = process.platform === 'linux' ? '/dev/stdin' : 'BACKJOON_011403.txt';
const input = require('fs').readFileSync(filePath).toString().trim().split(/\r?\n/);
const N = +input.shift();
const graph = input.map((i) => i.split(' ').map(Number));

function FloydWarshall(graph) {
  for (let m=0; m<N; m++)
  for (let s=0; s<N; s++)
  for (let e=0; e<N; e++)
    if (graph[s][m] && graph[m][e]) graph[s][e] = 1;
}


FloydWarshall(graph);
console.log(graph.map((i) => i.join(' ')).join('\n'));

 

 

ㅋㅋㅋㅋ 내가 처음부터 이렇게 풀었을 것 같나!!
나는 아직 C++에 편하고 js를 잘 다룰 줄 모른다! 그리고 플로이드 워셜 알고리즘보다 머리속에 있는 bfs를 통해서... 풀었다.
나의 해괴하고 더러운 코드가 보고 싶다면 열도록!

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

const T = Number(input[0]);
const array = [];

input.forEach((data, i) => {
  if(i === 0) return;
  data = data.split(" ").map((a) => Number(a));
  array.push(data);
})

const queue = [];
let queue_start_idx = 0;

for(let i=0; i<T; i++)
  for(let j=0; j<T; j++)
    if( array[i][j] ) bfs(i, j);

for(let i=0; i<T; i++)
  console.log(array[i].toString().replaceAll(",", " "))

function bfs(idx, k){
  const visited = Array.from({length: 100}, () => false);
  visited[k] = true;

  queue.push(k)

  let curr;
  while(queue.length > queue_start_idx) {
    curr = queue[queue_start_idx]; queue_start_idx++;

    for(let i=0; i<T; i++){
      if(visited[i] || array[curr][i] === 0) continue;
      queue.push(i);
      visited[i] = true;
      array[idx][i] = 1;
    }
  }
}