[프로그래머스]Summer/Winter Coding(~2018) : 배달 (level 3) (c++)

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

코딩테스트 연습 - 배달

 

bfs

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

const int INF = 987654321;

// 1번 마을에서 K의 시간내에 배달할 수 있는 마을 개수 구하기
int bfs(vector<vector<int>> &v_adj, int N, int K)
{
    // 1번 마을에서 N번째 마을까지의 최소 시간을 저장
    vector<int> min_dist(N + 1, INF);
    
    // 1번마을에서 0의 이동시간으로 시작
    queue<pair<int, int>> q;
    q.push({1, 0});
    min_dist[1] = 0;

    while (!q.empty())
    {
        // 현재 마을과 지금까지 이동한 시간
        int now = q.front().first;
        int time = q.front().second;
        q.pop();

        for (int next = 1; next <= N; ++next)
        {
            int n_time = v_adj[now][next];

            // 도로가 없으면 continue
            if (n_time == INF)
            {
                continue;
            }

            /*
                total = 지금까지 이동한 시간 + 다음마을까지 시간 
                
                total <= K이고, 1번마을에서 next마을까지의 최소 거리가 total보다 크면
                최소값 갱신 후 queue에 push
            */
            int total = time + n_time;
            if (total <= K && min_dist[next] > total)
            {
                min_dist[next] = total;
                q.push(make_pair(next, total));
            }
        }
    }

    int cnt = 0;
    for (int d : min_dist)
    {
        if (d != INF)
        {
            ++cnt;
        }
    }
    return cnt;
}

int solution(int N, vector<vector<int>> road, int K) {
   
    /*
        인접 배열 만들기
        A-B를 연결하는 도로가 여러개 있을 때, 최소의 값 저장 
    */
    vector<vector<int>> adj(N + 1, vector<int>(N + 1, INF));
    for (vector<int> &v : road)
    {
        if (adj[v[0]][v[1]] > v[2])
        {
            adj[v[0]][v[1]] = v[2];
            adj[v[1]][v[0]] = v[2];
        }
    }
    
    // 1번 마을에서 K의 시간내에 배달할 수 있는 마을 개수 구하기
    return  bfs(adj, N, K);
}

 

 

가중치있는 간선 배열이 주어진다.

 

가중치가 있는 그래프를 활용하는 문제이다. 

이 문제에서 주의해야할 사항은 2가지 이다.

 

1. 두 마을 A, B를 연결하는 도로는 여러 개가 있을 수 있다.

2. A - B까지 가는 경로가 여러개 있을 수 있고, 도로를 더 많이 거치는 경로가 더 빠를 수 있다.

 

1번은 문제에서 명시적으로 조건이 주어지므로, 처리하기가 쉽다.

하지만 2번의 경우는 예시나 문제지문에서 명시적으로 보여지지 않아

스스로 예외케이스를 생각해보아야 한다. 

 

2번의 경우 때문에 bfs로 N번 마을까지의 닿는 시간을 구할 때

min_dist로 최소시간을 매번 갱신해주어야 한다.

/*
    total = 지금까지 이동한 시간 + 다음마을까지 시간 
    
    total <= K이고, 1번마을에서 next마을까지의 최소 거리가 total보다 크면
    최소값 갱신 후 queue에 push
*/
int total = time + n_time;
if (total <= K && min_dist[next] > total)
{
    min_dist[next] = total;
    q.push(make_pair(next, total));
}