프로그래머스 문제 - 배달

프로그래머스 배달 문제 풀이를 진행하였습니다.

문제 해석

문제를 읽으면 아래와 같은 해석이 가능합니다.

최대 50개의 마을 갯수를 가집니다.
2000개 이하의 간선 정보를 입력받습니다.
1번 마을부터 시작하여 k값보다 작은 길이의 마을에만 배달이 가능합니다
배달 가능한 마을의 수를 구해야합니다

1번 마을로부터의 다른 마을의 최단 거리를 구하는 것이 중요해보입니다.

문제 풀이

마을 간의 거리를 더 빠르게 알기 위하여 간선 정보들을 2차원 배열에 미리 저장해둡니다.
문제에는 한 도로의 정보가 여러 번 중복되어 나오지 않는다 하였지만 테스트 케이스에는 중복한 값이 나왔으므로 더 적은 간선 값이 들어갈 수 있도록 프로그래밍합니다.

//배열 초기화
    for(int i = 1; i <= N; i++)
    {
        for(int j = 1; j <= N; j++)
        {
            if(i == j)
            {
                roadMap[i][j] = 0;
            }
            else
            {
                roadMap[i][j] = 100000000;
            }
        }
        dist[i] = 100000000;
    }
    
    //배열에 간선들 등록
    for(vector<int> v : road)
    {
        if(roadMap[v[0]][v[1]] > v[2])
        {
            roadMap[v[0]][v[1]] = v[2];
        }
        if(roadMap[v[1]][v[0]] > v[2])
        {
            roadMap[v[1]][v[0]] = v[2];
        }
    }

한 지점으로부터 다른 지점으로까지의 최단거리를 빠르게 계산하기 위해서는 다익스트라 알고리즘을 사용해야 합니다.
pair를 사용하여 현재 검색하는 마을과 지금까지 온 도로 거리 값들을 저장하며 다익스트라 알고리즘을 사용하였습니다.
우선순위 큐를 이용하면 쉽게 구현이 가능합니다.

//다익스트라 알고리즘 실행
    while(!pq.empty())
    {
        int cost = pq.top().first;
        int currentVillage = pq.top().second;
        pq.pop();
        for(int i = 1; i <= N; i++)
        {
            int nextCost = roadMap[currentVillage][i];
            if(dist[i] > cost + nextCost)
            {
                dist[i] = cost + nextCost;
                pq.push(make_pair(cost + nextCost, i));
            }
        }
    }

전체 코드

이번 문제는 다익스트라 알고리즘을 사용 방법을 익히는 문제였습니다.

#include <bits/stdc++.h>
#include <iostream>
#include <vector>
using namespace std;

int solution(int N, vector<vector<int> > road, int K) {
    int answer = 0;
    int roadMap[51][51] = {0,};
    priority_queue<pair<int, int>> pq;
    int dist[51];
    
    //배열 초기화
    for(int i = 1; i <= N; i++)
    {
        for(int j = 1; j <= N; j++)
        {
            if(i == j)
            {
                roadMap[i][j] = 0;
            }
            else
            {
                roadMap[i][j] = 100000000;
            }
        }
        dist[i] = 100000000;
    }
    
    //배열에 간선들 등록
    for(vector<int> v : road)
    {
        if(roadMap[v[0]][v[1]] > v[2])
        {
            roadMap[v[0]][v[1]] = v[2];
        }
        if(roadMap[v[1]][v[0]] > v[2])
        {
            roadMap[v[1]][v[0]] = v[2];
        }
    }
    
    dist[1] = 0;
    pq.push(make_pair(0, 1));
    
    //다익스트라 알고리즘 실행
    while(!pq.empty())
    {
        int cost = pq.top().first;
        int currentVillage = pq.top().second;
        pq.pop();
        for(int i = 1; i <= N; i++)
        {
            int nextCost = roadMap[currentVillage][i];
            if(dist[i] > cost + nextCost)
            {
                dist[i] = cost + nextCost;
                pq.push(make_pair(cost + nextCost, i));
            }
        }
    }
    
    //K값보다 작은 값들 수 체크
    for(int i = 1; i <= N; i++)
    {
         if(dist[i] <= K)
         {
             answer++;
         }
    }

    return answer;
}

출저

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