프로그래머스 [Lv. 3] 등산코스 정하기 {언어 : JavaScript} [다시 풀어 보기]

문제 링크

https://school.programmers.co.kr/learn/courses/30/lessons/118669?language=javascript

프로그래머스

정답 코드

function solution(n, paths, gates, summits) {
    let minP = 50001;  // 최소 강도로 도달할 수 있는 정상 번호 초기화
    let minV = 10000001;  // 최소 강도 초기화
    
    // 정상과 게이트를 쉽게 확인하기 위한 딕셔너리 생성
    const dictSG = {};
    for (const summit of summits) {
        dictSG[summit] = 1;  // 정상은 1로 표시
    }
    for (const gate of gates) {
        dictSG[gate] = 2;  // 게이트는 2로 표시
    }
    
    // 그래프 인접 리스트 생성
    const adjL = new Array(n+1).fill().map(() => []);
    for (const [i, j, w] of paths) {
        adjL[i].push([j, w]);
        adjL[j].push([i, w]);
    }

    // 방문 배열 생성
    let visited = Array(n+1).fill().map(() => 0);

    // BFS 함수 정의
    const bfs = (gate) => {
        const dq = [[gate, 0]];  // 시작지점과 초기 강도를 큐에 추가
        while (dq.length) {
            const [start, time] = dq.shift();
            if (minV < time) {  // 현재 강도가 최소 강도보다 큰 경우 가지치기
                continue;
            }
            for (const [peak, taken] of adjL[start]) {
                const vp = visited[peak];  // 다음 지점에 걸린 시간
                const maxIntensity = Math.max(time, taken);  // 최대 강도 계산
                // 정상에 도달한 경우 최소 강도 갱신
                if (dictSG[peak] === 1) {
                    if (minV > maxIntensity) {
                        minP = peak;
                        minV = maxIntensity;
                    } else if (minV === maxIntensity && minP > peak) {
                        minP = peak;
                        minV = maxIntensity;
                    }
                } 
                // 게이트에 도달한 경우 건너뛰기
                else if (dictSG[peak] === 2) {
                    continue;
                } else {
                    // 방문하지 않았거나, 더 작은 강도로 방문 가능한 경우 큐에 추가
                    if (vp === 0) {
                        visited[peak] = maxIntensity;
                        dq.push([peak, maxIntensity]);
                    } else if (vp > maxIntensity) {
                        visited[peak] = maxIntensity;
                        dq.push([peak, maxIntensity]);
                    }
                }
            }
        }
        return;
    }

    // 모든 게이트에서 BFS 수행
    for (const gate of gates) {
        bfs(gate);
    }

    // 결과 반환
    const answer = [minP, minV];
    return answer;
}

풀이 방법

 

1. 초기 설정
   • minP와 minV는 각각 최소 강도로 도달할 수 있는 정상의 번호와 강도를 저장하는 변수
   • dictSG 딕셔너리를 만들어 정상과 게이트를 쉽게 확인할 수 있도록 한다.
2. 그래프 구성
   • adjL 리스트를 만들어 각 노드와 연결된 다른 노드 및 그 사이의 거리를 저장한다.
   • visited 배열을 만들어 각 노드에 도달하는 데 걸린 최소 강도를 저장한다.
3. BFS 탐색
   • 각 게이트를 시작점으로 BFS를 수행한다.
   • BFS 큐에 시작점과 현재 강도를 넣고, 큐가 빌 때까지 반복한다.
   • 현재 노드에서 인접한 노드를 탐색하며, 인접 노드가 정상인 경우 최소 강도를 갱신한다.
   • 인접 노드가 게이트인 경우 건너뛰고, 이미 방문한 노드인 경우 최소 강도를 갱신한다.
4. 결과 반환
   • 모든 게이트에서 BFS를 수행한 후, 최소 강도로 도달할 수 있는 정상의 번호와 강도를 반환다.

 

느낀점

• 다시 풀라고 하면 풀 수 있지만 시간을 풀이 시간을 단축시켜야 한다. (2시간 이상 걸림)