[프로그래머스] Level 2. 배달

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

프로그래머스

 

해결 방법

1.  1번마을에서부터 각 마을까지의 최단거리를 구한다.
2. 각 거리가 K이하인 마을의 개수를 반환한다.
3. 최단거리를 구하는 방법은 다익스트라를 사용한다. 

주의사항

1. 이 문제에서는 최단거리 경로는 궁금하지 않고, 값만 궁금하므로, 이전노드를 저장하는 prev는 필요가없다!
2. 이 문제에서 도로는 양방향 도로이므로, map에 값을 넣을때 양방향 모두에 넣어줘야한다.
3. getIndex()함수는, 다음으로 검사할 마을을 찾는 함수이다. visited되지 않았으며, 현재까지 나온 거리테이블(dist) 중 가장 짧은 마을의 index를 반환한다.

#include <iostream>
#include <vector>
#include <climits>

using namespace std;

int getIndex(vector<int>& dist , vector<bool>& visited){
    int idx = -1;
    int d = INT_MAX;
    for(int i=0; i<dist.size(); i++){
        if(dist[i] == INT_MAX || visited[i]) continue;
        if(dist[i]< d){
            d = dist[i];
            idx = i;
        }
    }    
    return idx;
}
int solution(int N, vector<vector<int> > road, int K) {
    int answer = 0;
    //다익스트라 할거임..!
    vector<int> dist(N,INT_MAX);
    vector<bool> visited(N, false);
    
    //도로상황 저장, 양방향으로 모두 저장
    vector<vector<int>> maps(N,vector<int>(N,INT_MAX));
    for(int i=0; i<road.size(); i++){
        int s = road[i][0]-1; int e = road[i][1]-1; int d = road[i][2];
        maps[s][e] = maps[e][s] =  min(maps[s][e] , d);
    }
    
    dist[0] = 0; //0번째부터 시작
    while(true){
        int idx = getIndex(dist, visited);
        if(idx == -1) break;
        
        //연결된 노드들을 모두 검사.
        for(int i=0; i<maps[idx].size(); i++){
            if(maps[idx][i] == INT_MAX) continue;
            dist[i] = min(dist[i], dist[idx]+maps[idx][i]);
        }
        
        visited[idx] = true;
    }
    
    for(int i =0; i<dist.size(); i++){
        if(dist[i]<=K) answer ++;
    }
    return answer;
}

 

마무리하며

알고리즘에 숨도못쉬고있었는데 간만에 숨통 트이는 문제가 나와서 얼마나기쁜지 몰라 홍홍홍

다익스트라 실제로 구현해본건 처음이었는데, 대학교때 이론공부하던 짬으로 풀어내고 말았다. 다음 노드를 검사할 때 가장  dist가 짧은 노드를 검사한다는 것만 주의하면, 구현하는데는 어려움이 없었다.

 

참고로 다익스트라 알고리즘은 음의 가중치가 있을 경우, 제대로 동작하지 않는다. 만약 음의가중치가 있을 경우, 벨만포드 알고리즘을 사용해야한다. 

 

하지만 레벨2에서 나올일은 없겠지.