작성일 : November 3, 2021

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

해설 : https://msko.tistory.com/9

나의 풀이

그래프 문제를 어떻게 접근해야 할지 몰랐다..

풀이 해설

 function solution(N, road, K) {
      // 1. 노드별 거리를 무한으로 하는 배열 생성(1부터 사용하기 위해 N+1의 배열 생성) 
			//    인접한 노드별 시간(가중치)의 정보를 담고 있는 배열 생성
    const dist = Array(N + 1).fill(Infinity);
    const adj = Array.from({ length: N + 1 }, () => []);

      // 1-1. 인접한 노드별 시간(가중치)의 정보를 담고 있는 배열에 데이터 추가
    road.forEach(([a,b,c]) => {        
        adj[a].push({ to: b, time: c }); 
        adj[b].push({ to: a, time: c }); 
    });

      // 2.1번 마을에서부터 우선순위 큐 시작 및 초기값 0 할당(시작점이기 때문에)
    const pq = [{ to: 1, time: 0 }];
    dist[1] = 0;

      // 3.우선순위 큐 배열에 값이 없을 때까지 반복
    while(pq.length) {
        let {to, time} = pq.pop();

          // 4. 연결된 노드에서의 값이 현재의 값 + 해당 노드의 시간(가중치) 보다 클 경우, 
				  //    값을 대체하고 우선순위 큐에데이터 추가
        adj[to].forEach(next => {
            if(dist[next.to] > dist[to] + next.time) {
                dist[next.to] = dist[to] + next.time;
                pq.push(next);
            }
        })
    }

      // 5.
    return dist.filter((item) => item <= K ).length;
}

후기

완벽한 이해를 하지 못하고 포기했다. 우선순위 큐 부터 이해를 마쳐야겠다..