배달(최단 거리 알고리즘)

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

오늘은 이 문제를 가지고 최단 거리를 구하는 알고리즘을 공부할 예정이다. 이 문제를 풀다가 문제가 간결하고 공부하기 좋을 듯해 가져왔다.

최단 거리 알고리즘

1. 다익스트라
2. 벨만-포드
3. 플로이드-와샬

다익스트라

다익스트라 알고리즘으로 먼저 풀었다.

1. Edge 구조체를 만든다. 구조체에는 정점과 지금까지 구한 해당 정점까지의 최단 거리를 담는다. 우선순위 큐에 넣어 최소힙을 만들 예정이기 때문에 operator< 함수를 만든다.

struct Edge
{
	int point;
    int price;
    Edge(int a, int b)
    {
    	point = a;
        price = b;
    }
    bool operator<(const Edge& b) const
    {
    	return price > b.price;
    }
};

2. price 배열 하나를 정점의 개수만큼 2147000000 초기화해준다.

vector<int> prices(N + 1, 2147000000);

3. vector<pair<int, int>> graph[51]에 정점 연결 정보를 넣는다.
4. 출발 정점이 1이라면 price[1] = 0 대입하여 우선순위 큐에 넣어준다.

priority_queue<Edge> pQ;
pQ.push(Edge(1, 0));
prices[1] = 0;

5. pQ의 사이즈가 0이 될 때까지 while문을 반복한다.

while(!pQ.empty())
{
	// 부모 정점에서 e.point로 가는 비용은 e.price이다.
	Edge e = pQ.top();
    pQ.pop();
    
    // 예: 5번 정점으로 가는 비용이 이미 더 작은 값으로 갱신되어 있는 상태에서는 아래 구문을 실행하지 않는다.
    if(e.price > prices[e.point]) continue;
    for(int i = 0; i < graph[e.point].size(); ++i)
    {
    	int next = graph[e.point][i].first;
        int nextPrice = e.price + graph[e.point][i].second;
        
        if(prices[next] > nextPrice)
        {
        	prices[next] = nextPrice;
            pQ.push(Edge(next, nextPrice);
        }
    }
}

6. prices 배열에서 K값 이하의 개수만큼 answer를 리턴한다.

풀이

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

using namespace std;

vector<pair<int, int>> graph[51];

struct Edge
{
    int point;
    int price;
    Edge(int a, int b)
    {
        point = a;
        price = b;
    }
    bool operator<(const Edge& b) const
    {
       return price > b.price;
    }
};

int solution(int N, vector<vector<int> > road, int K) {
    int answer = 0;
    
    vector<int> prices(N + 1, 2147000000);
    
    for(int i = 0; i < road.size(); ++i)
    {
        int a, b, c;
        a = road[i][0];
        b = road[i][1];
        c = road[i][2];
        graph[a].push_back(make_pair(b, c));
        graph[b].push_back(make_pair(a, c));
    }
    
    priority_queue<Edge> pQ;
    
    pQ.push(Edge(1, 0));
    prices[1] = 0;
    
    while(!pQ.empty())
    {
        Edge e = pQ.top();
        pQ.pop();
        
        if(e.price > prices[e.point]) continue;
        for(int i = 0; i < graph[e.point].size(); ++i)
        {
            int next = graph[e.point][i].first;
            int nextPrice = e.price + graph[e.point][i].second;
            
            if(prices[next] > nextPrice)
            {
                prices[next] = nextPrice;
                pQ.push(Edge(next, nextPrice));
            }
        }
    }
    
    for(int i = 1; i <= N; ++i)
    {
        if(K >= prices[i]) ++answer;
    }
    
    return answer;
}

---

벨만-포드

1번 정점에서 5번 정점으로 가는 경우에 간선 1번 만에 가는 경우, 2번 만에 가는 경우, 3번 만에 가는 경우, 4번 만에 가는 경우를 계산한다.(정점이 5개라면 간선을 4개 거치는 경우가 가장 많은 간선을 거치는 경우이다. 만약 5개를 거칠 때 더 작아진다면 음의 사이클이 존재하는 그래프이다.)

벨만-포드 알고리즘은 음의 사이클의 그래프에는 적절하지 않다. 정점이 n개일 때, n개의 간선을 거치는 경우를 계산하고 값이 갱신된다면 음의 사이클이 있다고 판단한다.

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

struct Edge
{
    int e, val;
    Edge(int a, int b)
    {
        e = a;
        val = b;
    }
};

int solution(int N, vector<vector<int> > road, int K) {
    int answer = 0;
    
    vector<Edge> Ed[51];
    for(int i = 0; i < road.size(); ++i)
    {
        int s = road[i][0];
        int e = road[i][1];
        int val = road[i][2];
        Ed[s].push_back(Edge(e, val));
        Ed[e].push_back(Edge(s, val));
    }
    
    vector<int> dist(N + 1, 2147000000);
    dist[1] = 0;
    
    // i개의 정점을 거쳤을 때 최단 거리를 구한다.
    for(int i = 1; i < N; ++i)
    {
        for(int j = 1; j <= N; ++j)
        {
            for(int k = 0; k < Ed[j].size(); ++k)
            {
                int e = Ed[j][k].e;
                int val = Ed[j][k].val;
                
                if(dist[j] != 2147000000 && dist[j] + val < dist[e])
                {
                    dist[e] = dist[j] + val;
                }
            }
        }
    }
    
    // 음의 사이클 확인.
    for(int j = 1; j <= N; ++j)
    {
        for(int k = 0; k < Ed[j].size(); ++k)
        {
            int e = Ed[j][k].e;
            int val = Ed[j][k].val;
                
            if(dist[j] != 2147000000 && dist[j] + val < dist[e])
            {
                // 만약에 더 적은 값이 된다면 음의 사이클이 존재한다.
                return answer = -1;
            }
        }
    }
    
    for(int i = 1; i <= N; ++i)
        if(K >= dist[i]) ++answer;

    return answer;
}

---

플로이드-워샬

다익스트라와 벨만-포드는 한 정점에서 다른 정점으로 가는 최소 비용을 구하는 알고리즘이다. 반면에 플로이드-워샬은 모든 정점에서 모든 정점으로 가는 최소 비용을 구한다.

따라서 다이나믹 테이블은 2차원이어야하며 점화식을 구해야한다.

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

int solution(int N, vector<vector<int> > road, int K) {
    int answer = 0;

    vector<vector<int>> graph(N + 1, vector<int>(N + 1, 500001));
    for(int i = 1; i <= N; ++i) graph[i][i] = 0;
    
    // 1. 인접 행렬을 만든다.
    for(int i = 0; i < road.size(); ++i)
    {
        int s = road[i][0];
        int e = road[i][1];
        int dist = road[i][2];
        
        // [3,5,2],[3,5,3]의 경우를 고려해야 한다.
        graph[s][e] = graph[s][e] < dist ? graph[s][e] : dist;
        graph[e][s] = graph[e][s] < dist ? graph[e][s] : dist;
    }
    
    // 2. 1번 정점을 거쳐 갈 경우, 2번 정점을 거쳐 갈 경우...
    // 점화식: 최단 거리는 graph[i][j] || graph[i][k] + graph[k][j];
    for(int i = 1; i <= N; ++i)
    {
        // j 정점에서 k 정점으로 갈 때 i번 정점을 거쳐갈 경우를 2중 for문을 돌며 계산.
        for(int j = 1; j <= N; ++j)
        {
            for(int k = 1; k <= N; ++k)
            {
                graph[j][k] = graph[j][k] < graph[j][i] + graph[i][k] ? 
                    graph[j][k] : graph[j][i] + graph[i][k];
            }
        }
    }
    
    for(int i = 1; i <= N; ++i)
    {
        if(K >= graph[1][i]) ++answer;
    }
    
    return answer;
}

---

꼭 다시 풀기!