[프로그래머스#JS] 배달

문제

https://programmers.co.kr/learn/courses/30/lessons/12978

코드

function solution(N, road, K) {
  let adj = Array.from(Array(N + 1), () => new Array(N + 1).fill(Infinity));
  let answer = 0;

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

  
  road.forEach((r) => {
    const [s, e, dist] = r;

    // 중복 제거
    if (adj[s][e] !== Infinity) {
      adj[s][e] = adj[e][s] = Math.min(adj[s][e], dist);
    } else {
      adj[s][e] = adj[e][s] = dist;
    }
  });

  // 와샬 알고리즘
  for (let k = 1; k <= N; k++) {
    for (let i = 1; i <= N; i++) {
      for (let j = 1; j <= N; j++) {
        if (adj[i][k] + adj[k][j] < adj[i][j]) {
          adj[i][j] = adj[i][k] + adj[k][j];
        }
      }
    }
  }

  for (let i = 1; i <= N; i++) {
    if (adj[1][i] <= K) answer++;
  }

  return answer;
}

1번 마을에서 시작하는 지 모르고 플로이드 와샬 알고리즘을 썼는데 시간초과가 안걸리고 맞았다. 마을-마을 간 이동 경로가 두 개인 경우를 체크 못해서 푸는 시간이 오래 걸렸다.