C++:: 프로그래머스 < 배달 >

주어진 마을들이 이어진 경로를 바탕으로 1번 마을에서 K이하 시간까지
걸리는 마을의 개수를 리턴해주면 되는 문제이다. 큰맥락은 어렵지 않지만, 자잘하게 예외처리를 해주어야 해서 조금 번거로울 수 있는 문제이다.

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

int solution(int N, vector<vector<int> > road, int K) {
    int answer = 1;
    vector<int> vis(N+1, 0);
    vector<vector<pair<int,int>>> roads(N+1);
    for (auto r : road) {// 마을에서 마을 정보 저장
        roads[r[0]].push_back({r[1],r[2]});
        roads[r[1]].push_back({r[0],r[2]});
    }
    queue<pair<int, int>> q; q.push({1,0});// 1번마을부터 시작
    while (!q.empty()) {
        pair<int, int> cur = q.front(); q.pop();
        // 이전에 방문한적이 있는데 현재걸린 시간이 더 크거나 같거나, 주어진 시간 초과면
        if ((vis[cur.first] != 0 && vis[cur.first] < cur.second) || cur.second > K)
            continue ;
        vis[cur.first] = cur.second;// 걸린시간 기입
        for (auto next : roads[cur.first]) {
            if (next.first != 1)// 1번마을 경우 걸린시간이 0 이어서 예외처리
                q.push({next.first, cur.second + next.second});
        }
    }
    for (auto v : vis) if (v) answer++;
    return answer;
}