[JS][백준]1719_택배

문제 번호

1719번: 택배

 

 

 

알고리즘 분류

• 그래프 이론
• 다익스트라
• 플로이드–와샬

 

문제 풀이

 다익스트라와 플로이드-와샬 알고리즘을 고민하다가 플로이드-와샬이 좀더 친숙해서 플로이드-와샬로 문제를 풀었다.

i 에서 j 로 갈때 k를 거쳐서 가는것이 더 비용이 적게들면 arry[i][j]의 값을 수정한다는 플로이드-와샬의 내용을 살짝 응용하면 된다. 

 

 city라는 2차원 배열을 생성해서 문제에서 주어진 집하장간의 경로를 입력하고 플로이드-와샬 알고리즘에 사용하여 집하장간의 최소값을 갱신하였다. 

 그런데 여기서 한가지 추가적으로 해주어야하는 일이 있다. 우리는 최소비용을 구하는것이 아니라 최소비용일때 '처음으로 들리는 집하장' 을 알아야한다. 그래서 i 에서 j 로 갈때 처음으로 들리는 집하장을 기록할 answer이라는 2차원 배열을 사용하기로 했다. answer[i][j] = 2 라면 i 에서 출발하여 j 로 갈때 처음으로 들리는 집하장은 2번 집하장 이라는 뜻이다.

 

 시간초과에 걸릴까봐 routeTable 이라는 변수에 집어넣어서 한번에 출력했다.

 

전체코드

function sol(n, city, answer){
  let routeTable = ''

  // floyd
  for(let k=1; k<=n; k++){
    for(let i=1; i<=n; i++){
      for(let j=1; j<=n; j++){
        if(city[i][j] > city[i][k] + city[k][j]){
          city[i][j] = city[i][k] + city[k][j];
          answer[i][j] = answer[i][k]; // k를 거쳐서 가는것이 더 빠르다면 answer 배열을 갱신해야한다.
        }
      }
    }
  }
  
  for(let row=1; row<=n; row++){    
    for(let col=1; col<=n; col++){
      if(row === col) 
        routeTable += '-' + ' ';
      else{
        routeTable += answer[row][col] + ' ';
      }
    }
    routeTable += '\n';
  }
  console.log(routeTable);
}

function insert(){
  const input = require('fs').readFileSync('택배/input.txt').toString().trim().split('\n');
  const [n,m] = input[0].split(' ').map(Number);
  let city = new Array(n+1).fill(null).map(_ => new Array(n+1).fill(Infinity));
  let answer = new Array(n+1).fill(null).map(_ => new Array(n+1).fill([]));
  for(let i=1; i<=m; i++){
    let [to,from,weigth] = input[i].split(' ').map(Number);
    city[to][from] = weigth;
    city[from][to] = weigth;
    answer[to][from] = from;
    answer[from][to] = to;
  }
  sol(n, city, answer);
}
insert();

 

 

특이사항