풀이과정
각 부대원들이 부대로 복귀하는 최단경로를 찾는 문제인데, bfs를 통해 각 부대원별로 목적지까지 최단 경로를 구하려다보니 시간초과가 발생했다.
아래는 시간 초과가 발생한 코드
function solution(n, roads, sources, destination) {
const answer = [];
const graph = [...Array(n+1)].map(()=>[]);
for(const road of roads){
const [a,b] = road;
graph[a].push(b);
graph[b].push(a);
}
// source에서부터 graph를 순회하여 destination에 도착하는 최단거리를 구하는 bfs 함수
function bfs(start){
if(start === destination) return 0;
const visited = [...Array(n+1)].map(()=>false);
const q = [[start, 0]];
visited[start] = true;
while(q.length){
const [currentRegion, count] = q.shift();
// area 도시에 연결된 도시들을 방문했는지 체크하고 이동
for(const region of graph[currentRegion]){
if(region === destination) return count + 1;
if(!visited[region]){
q.push([region, count+1]);
visited[region] = true;
}
}
}
return -1;
}
for(const i of sources){
answer.push(bfs(i))
}
return answer;
}
어떻게 효율성을 개선할 수 있을지 고민하다가 목적지는 하나이기에 결국 목적지로부터 부대원으로 가는 길을 찾으면 bfs를 한번만 실행하더라도 문제를 해결할 수 있음을 깨달았다.
정답코드
function solution(n, roads, sources, destination) {
const answer = [];
const graph = [...Array(n+1)].map(()=>[]);
for(const road of roads){
const [a,b] = road;
graph[a].push(b);
graph[b].push(a);
}
// source에서부터 graph를 순회하여 destination에 도착하는 최단거리를 구하는 bfs 함수
function bfs(start){
if(start === destination) return 0;
const visited = [...Array(n+1)].map(()=>false);
const q = [[start, 0]];
visited[start] = true;
while(q.length){
const [currentRegion, count] = q.shift();
// area 도시에 연결된 도시들을 방문했는지 체크하고 이동
for(const region of graph[currentRegion]){
if(region === destination) return count + 1;
if(!visited[region]){
q.push([region, count+1]);
visited[region] = true;
}
}
}
return -1;
}
for(const i of sources){
answer.push(bfs(i))
}
return answer;
}
'알고리즘 문제풀이' 카테고리의 다른 글
프로그래머스 - 연속된 부분 수열의 합 (0) | 2023.12.02 |
---|---|
프로그래머스 - 다단계 칫솔 판매 (0) | 2023.12.01 |
백준 - 1406 에디터 (1) | 2023.11.24 |
백준 - 1912 연속합(Javascript) (1) | 2023.11.21 |
백준 silver 3 - 1463 1로 만들기(Javascript) (0) | 2023.11.20 |