Programmers / Level 2 / 배달 / JS

문제 간단설명

N개의 마을로 이루어진 나라가 있다. 이 나라의 각 마을에는 1부터 N까지의 번호가 부여되어있다.

각 마을은 양방향 도로로 연결되어 있는데, 도로를 지날 때 걸리는 시간은 도로별로 다르다.

1번 마을에서 각 마을로 음식 배달을 하려고 하는데, K 시간 이하로 배달이 가능한 마을에서만 주문을 받으려고 한다.

주문을 받을 수 있는 마을의 개수를 반환하면 된다.

 

제한 사항

• 1 <= N <= 50
• 1 <= road.length <= 2,000
• road는 길이가 3인 배열이며, 순서대로 (a, b, c)를 나타낸다.
  • a, b(1 <= a, b <= N, a != b)는 도로가 연결하는 두 마을의 번호이며, c(1 <= c <= 10,000, c는 자연수)는 도로를 지나는데 걸리는 시간이다.
  • 두 마을 a, b를 연결하는 도로는 여러 개가 있을 수 있다.
  • 한 도로의 정보가 여러 번 중복해서 주어지지 않는다.
• 1 <= K <= 500,000
• 임의의 두 마을간에 항상 이동 가능한 경로가 존재한다.
• 1번 마을에 있는 음식점이 K 이하의 시간에 배달이 간으한 마을의 개수를 반환하면 된다.

 

실패 코드

function solution(N, road, K) {
    const adjMatrix = Array.from({ length: N + 1 }, () => Array.from({ length: N + 1 }, () => Infinity));
    
    const makeAdjMatrix = () => {        
        for(let i=0; i<road.length; i++) {
            for(let j=0; j<N; j++) {
                const [start, end, time] = road[i];
        
                adjMatrix[start][end] = adjMatrix[start][end], time;
                adjMatrix[end][start] = adjMatrix[end][start], time;
            }
        }
    }
    
    const floydWarshall = () => {
        for(let k=1; k<=N; k++) {
            for(let i=1; i<=N; i++) {
                for(let j=1; j<=N; j++) {
                    if(adjMatrix[i][k] + adjMatrix[k][j] < adjMatrix[i][j]) {
                        adjMatrix[i][j] = adjMatrix[i][k] + adjMatrix[k][j];
                    }
                }
            }
        }
    }
    
    let result = 0;
    const getResult = () => {
        for(let i=1; i<=N; i++) {
            if(adjMatrix[1][i] <= K) {
                result++;
            }
        }
    }
    
    makeAdjMatrix();
    floydWarshall();
    getResult();
    
    return result;
}

 

 

위 코드엔 빠진 로직이 2가지가 있다. (문제를 좀 더 꼼꼼히 읽었어야 했다...)

 

첫번째로, 많은 분들이 실수했을 만한 현재 있는 곳으로 가는 시간은 0으로 초기화해주어야 한다. 라는 것이다...

 

두번째는 제한 사항에 나와있다. 제한 사항에 보면 "두 마을 a, b를 연결하는 도로는 여러 개가 있을 수 있다." 라고 되어있다. 어차피 우리는 최소 시간을 구해야하기 때문에, 같은 경로의 여러 도로가 존재하면 최소 시간만을 가지는 도로만 저장하면 된다.

 

위 두 조건을 추가하면 아래와 같이 성공 코드를 만들 수 있다.

 

성공 코드

function solution(N, road, K) {
  const adjMatrix = Array.from({ length: N + 1 }, () =>
    Array.from({ length: N + 1 }, () => Infinity)
  );

  /**
   * 인접행렬을 만드는 함수이다.
   */
  const makeAdjMatrix = () => {
    // 자기 자신으로 가는 시간은 0이기 때문에 0으로 초기화 해준다.
    for (let i = 0; i < N; i++) {
      for (let j = 0; j < N; j++) {
        if (i === j) {
          adjMatrix[i][j] = 0;
        }
      }
    }

    for (let i = 0; i < road.length; i++) {
      for (let j = 0; j < N; j++) {
        const [start, end, time] = road[i];

        // 양방향으로 연결되어 있기 때문에 양방향으로 초기화 해준다.
        // 같은 경로에 대해 여러 도로가 있을 수 있으므로 최소값만 저장해준다.
        adjMatrix[start][end] = Math.min(adjMatrix[start][end], time);
        adjMatrix[end][start] = Math.min(adjMatrix[end][start], time);
      }
    }
  };

  /**
   * Floyd-Warshall 알고리즘으로 최단거리를 구하는 함수이다.
   */
  const floydWarshall = () => {
    for (let k = 1; k <= N; k++) {
      for (let i = 1; i <= N; i++) {
        for (let j = 1; j <= N; j++) {
          if (adjMatrix[i][k] + adjMatrix[k][j] < adjMatrix[i][j]) {
            adjMatrix[i][j] = adjMatrix[i][k] + adjMatrix[k][j];
          }
        }
      }
    }
  };

  let result = 0;
  const getResult = () => {
    for (let i = 1; i <= N; i++) {
      if (adjMatrix[1][i] <= K) {
        result++;
      }
    }
  };

  makeAdjMatrix();
  floydWarshall();
  getResult();

  return result;
}

 

Floyd-Warshall 알고리즘을 통해 답을 구했다. 이 알고리즘은 그래프 탐색시에 가중치가 있는 경우 사용하면 좋은 알고리즘이다. 이 알고리즘은 모든 정점 쌍 간의 최단 경로를 찾는 그래프 알고리즘으로, 중간 정점을 경유하는 경로를 고려하여 모든 가능한 경로를 탐색한다.

 

floydWarshall 함수를 보면 3중 반복문이 들어간 것을 볼 수 있다. 이 알고리즘은 O(n^3)의 시간복잡도를 가진다.

하지만, 문제에서 주어진 N의 최대가 50이므로 125,000 밖에 되지 않아서 이 알고리즘으로 풀이가 가능했다.