정점 사이의 간선의 길이가 1로 정해져 있다.
이게 유동적이면 bfs로 해결할 수 없지만 (다익스트라, 플로이드 와샬 등 사용으로 해결)
1로 일정하기에 bfs로 풀었다.
1. graph에 경로들을 담아두고
2. bfs 돌리면서 visited의 최소 시간으로 방문한 값을 저장하다.
3. map 돌리면서 출력
function solution(n, roads, sources, destination) {
const graph = new Array(n+1).fill(null).map(_=>[]);
for(let [a,b] of roads){
graph[a].push(b);
graph[b].push(a);
}
const visited = new Array(n+1).fill(Infinity);
const bfs = (destination) =>{
const q = [destination];
visited[destination] = 0;
while(q.length > 0){
const idx = q.shift();
for(let newIdx of graph[idx]){
if(visited[idx]+1 < visited[newIdx]){
visited[newIdx] = visited[idx]+1;
q.push(newIdx);
}
}
}
}
bfs(destination);
return sources.map(v=>{
if(visited[v] === Infinity) return -1;
else return visited[v];
});
}
반응형
'Algorithm > Programers' 카테고리의 다른 글
프로그래머스 카운트 다운 javascript (0) | 2022.10.10 |
---|---|
프로그래머스 멀리 뛰기 javascript (0) | 2022.09.05 |
프로그래머스 방문 길이 javascript (0) | 2022.09.03 |
프로그래머스 숫자 블록 javascript (0) | 2022.09.03 |
프로그래머스 N-Queen javascript (0) | 2022.08.28 |
댓글