[BFS] 배달 - Summer/Winter Coding(~2018)

제대로 동작하도록 구현하는건 쉽지만 시간 초과에 막힐 수 있는 문제다.

이 문제는 최대한 효율적으로 구현해야 한다.

 

해결 방법

필자는 BFS로 해결했다.

Step1) 이 문제는 인접한 두 노드를 연결하는 간선이 여러개가 있을 수 있다. 그래서 인접한 두 노드를 연결하는 최소 비용의 간선들을 저장해둬야 한다.

Step2) 노드와 간선을 연결한다.

Step3) BFS를 수행하면서 1번 노드(마을)로부터의 최소 비용(시간)이 갱신된 노드만 Queue에 넣는다. 참고로, 갱신된 노드의 비용이 K를 넘어가는 경우에는 굳이 Queue에 넣지 않도록 처리하면 처리시간을 단축할 수 있다.

Step4) 1번 노드로부터의 최소 비용이 K 이하인 노드를 모두 카운트한다. 단, 1번 노드는 당연히 카운트 해야하고, BFS를 통해 한번도 방문하지 않은 노드들은 카운트하지 않아야 한다.

 

 

소스 코드

#include <vector>
#include <queue>
using namespace std;

queue<int> q;
int cost[51][51]; // 인접한 두 노드 사이의 최소 비용의 간선
vector<int> v[51]; // 노드와 간선을 연결한 정보
int ans[51]; // 1번 노드로부터의 최소 비용

int solution(int N, vector<vector<int> > road, int K) {
    int answer = 1;
    bool updated;
    int s, d;
    
    // 인접한 두 노드를 연결하는 최소 비용의 간선을 구함
    for(int i=0;i<road.size();i++){
        s=road[i][0]; d=road[i][1];
        if(cost[s][d]==0||road[i][2]<cost[s][d]) {
            cost[s][d]=road[i][2];
            cost[d][s]=road[i][2];
        }
    }
    
    // 간선 연결
    for(int i=0;i<road.size();i++){
        v[road[i][0]].push_back(road[i][1]);
        v[road[i][1]].push_back(road[i][0]);
    }
    
    // BFS
    q.push(1);
    while(!q.empty()){
        int f=q.front();
        q.pop();
        for(int i=0;i<v[f].size();i++){
            int x=v[f][i];
            if(x==1) continue;
            updated=false;
            if(ans[x]==0||ans[f]+cost[f][x]<ans[x]) {
                ans[x]=ans[f]+cost[f][x];
                updated=true;
            }
            if(!updated||ans[x]>K) continue;
            q.push(x);
        }
    }
    for(int i=2;i<N+1;i++) if(ans[i]!=0&&ans[i]<=K) answer++;
    return answer;
}

 

테스트케이스 32개 모두 정답