[Javascript/PGS] Lv.3 : 부대복귀

 

https://school.programmers.co.kr/learn/courses/30/lessons/132266#

프로그래머스

---

프로그래머스 레벨 3.

최단거리를 보고 BFS 문제겠거니 추측하였다.

보통 좌표(?)가 주어지는 문제는 너비우선탐색으로 최단거리를 찾기 때문에,,ㅎㅎ

 

 

1. 첫 시도 - 테스트케이스 11번~15번 시간초과

 

 

 

왜 초과가 났나 했는데 😢

JS로 알고리즘 푸는게 익숙하지 않아서 bfs를 반복문에 넣어버린 탓이었다.

바꾸는 김에 다른 코드들도 조금씩 더 짧고 효율적으로 변경해보았다.

(Map.get 으로 데이터 유무 확인 -> Map.has로 확인하는 등)

---

 

2. 두번째 시도 - 성공

 

중요한 아이디어 중 하나는, 출발지부터 탐색하는게 아니라 도착지부터 탐색하는게 효율적이라는 것이다.

도착지는 1개로 고정이기 때문에, 도착지부터 거꾸로 끝까지 탐색하면서 각 노드까지의 거리를 저장한 다음

마지막에 필요한 노드의 거리값만 추출하면 된다.

 

 

나의 풀이

let answer = [];
let roadmap = new Map();

const bfs=(destination, time, sources, n)=>{
    let visited = new Array(n+1).fill(-1); // 기본값을 -1로
    let q = [];
    q.push([destination, time]); // 현재 노드와 횟수를 함께 저장
    visited[destination] = 0;

    while(q.length>0){
        let [now, count] = q.shift();
        let nowEdges = roadmap.get(now);
        if(!nowEdges) continue;
        nowEdges.forEach(e=>{
            if(visited[e]<0){
                q.push([e, count+1]);
                visited[e] = count+1;
            }
        })
    }
    answer = sources.map(s => visited[s]);
    return;
}

function solution(n, roads, sources, destination) {
    
    roads.forEach(([a, b])=>{ // 엣지 양방향 저장
        if(roadmap.has(a)) roadmap.set(a, [...roadmap.get(a), b]);
        else roadmap.set(a, [b]);
        
        if(roadmap.has(b)) roadmap.set(b, [...roadmap.get(b), a]);
        else roadmap.set(b, [a]);
    })
    bfs(destination, 0, sources, n);
    return answer;
}

 

 

지금 감기약을 먹고 있는데.. 확실히 머리가 잘 안돌아간다.

얼른 컨디션 회복해야겠다 ㅠㅠ