공부하는 식빵맘 👱‍♀️

공부하는 식빵맘 👱‍♀️

반갑습니다 :)

[C++로 풀이] 배달 (최단 경로, 다익스트라, 우선순위 큐를 써야하는 이유)⭐⭐⭐

Date:     Updated:

카테고리:

태그:

📌 배달

난이도 ⭐⭐⭐

🚀 문제

image

image


🚀 내 풀이 ⭕

최단 경로 알고리즘 👉 다익스트라 알고리즘 사용함

  • 최단 경로 알고리즘
    • 정해놓은 특정 정점 1개에서 출발하여 모든 정점들의 순회하며, 특정 정점에서 해당 정점들까지의 최단 경로를 업데이트한다. 👉 다익스트라가 적합
      • 출발지는 1 번 마을 고정이며 1 번 마을에서 그 외 마을들까지의 최단 경로(문제에선 시간)를 재고 이 최단 경로가 K 이하가 되는 마을을 카운팅하면 되는 문제이다.
      • 마을(정점V)의 개수는 최대 50개이고, 도로(간선E)의 개수는 최대 2000개이다. 정점 당 모든 도로들을 검사하는 것만 해도 O(VE) = O(100,000) 이 되기 때문에 백트래킹으로 K이하가 되는 시간을 일일이 구해보다가 되돌아오기를 반복하는 것은 시간 복잡도 상 부담스러운 일이 될 것이라고 생각했다.
  • 처음엔 문제를 대충 스윽 보고 최소 신장 트리 MST 문제인가 생각했었다. 근데 MST 는 무조건 그리디하게 작은 가중치를 가진 간선부터 선택해나가기 때문에 “최단 경로”와는 거리가 좀 있다. 무조건 가중치가 작은 간선을 선택한다고 그 경로가 최단 경로가 되는 것은 아니기 때문이다. 예를 들어 1-2-2 간선을 타는 것은 최소 신장 트리에는 만족하겠지만 사실 최단 경로는 1-3 간선을 타는 것이 될 수도 있기 때문이다.
  • 다음에 방문할 후보들이 되는 정점들의 최단 경로는 언제든지 새롭게 업데이트 될 수 잇다.
    • 우선순위 큐를 사용하면 최단 경로를 가진 정점부터 방문할 수 있도록 할 수 있다.
      • 우선순위 큐의 정렬 기준을 정점의 최단 경로를 기준으로 정렬되게끔 설정하면 언제나 최단 경로가 가장 짧은 정점부터 pop 되기 때문이다.
      • 그리고 그 당시 상황에서의 최단 경로 값을 새롭게 매번 업데이트 할 때마다 계속 힙정렬이 되기 때문에 우선순위 큐는 언제나 최단 경로가 가장 짧은 정점부터 pop 되는게 보장된다.
        • 여담으로 C++에서 제공하는 priority_queue 는 큐에 들어가있는 원소를 수정할 수 없다. (L-value 로서 그 원소를 참조중이라면 모를까.. R-value로 넣은 원소라면..불가능..!) vector나 배열같이 임의 접근이 불가능하기 때문이다. 그래서 해당 정점로 가는 경로를 더 짧은걸 발견했다면 큐 안에 있는 객체의 최단경로 값을 수정할 수는 없으니 그냥 별개의 정점 객체를 새로 만들어서 그 정점과 데이터(ex. 좌표)는 같지만 최단 경로는 더 짧은 별개의 객체로서 큐에 삽입 한다. 어차피 우선순위 큐 특성상 더 짧은 경로를 가진 정점 객체부터 pop 을 하니, 남아 있는 중복되는, 더 긴 경로를 가진 객체는 이미 방문 했었다고 처리하여 거르면 된다.
      • 어떤 경로가 되느냐에 따라, 현재 어떤 정점을 방문 중이며 이걸 경유하느냐 안하냐에 따라 이제까지 최단 경로라고 생각해왔던게 뒤엎어질 수도 있다. 매번 새롭게 그때 그때 상황에 맞춰 아직 방문되지 않은 정점들의 최단 경로를 업데이트 해나간다.
        • distance[n] = min(distance[n], distance[m] + E(m, n)) 👉 Dynammic Programming 방식이다. n까지 가는데에 m 정점을 경유하는게 더 최단경로가 된다면 업데이트 하고(n은 m과 연결되어 있다는 전제 하) 아니면 원래 구해놓은 최단 경로로 냅둠.
        • 그래서 언제나 가장 짧은 경로를 가진 정점부터 방문하기 때문에 이 정점까지의 경로는 늘 “현재 까지에서의 최단 경로”라는 것이 유지된다.
#include <iostream>
#include <vector>
#include <queue>
using namespace std;

struct Town {
    int number;
    int shortestTime;

    Town() {}

    Town(int _number, int _shortestTime) {
        number = _number;
        shortestTime = _shortestTime;
    }
};

struct cmp {
    bool operator()(const Town& a, const Town& b) {
        return a.shortestTime > b.shortestTime;
    }
};

int solution(int N, vector<vector<int>> road, int K) {
    int answer = 0;
    const int maxTime = 20000000;
    
    vector<bool> visited(N + 1);
    vector<int> time(N + 1, maxTime);
    priority_queue<Town, vector<Town>, cmp> pq;

    time[1] = 0;
    pq.push(Town(1, 0));

    while (!pq.empty()) {
        
        Town startTown = pq.top();
        pq.pop();

        if (visited[startTown.number])
            continue;

        visited[startTown.number] = true;

        for (int i = 0; i < road.size(); ++i) {
            
            Town nextTown;
            if (road[i][0] == startTown.number)
                nextTown.number = road[i][1];
            else if (road[i][1] == startTown.number)
                nextTown.number = road[i][0];
            else
                continue;

            if (visited[nextTown.number])
                continue;

            if (time[nextTown.number] < startTown.shortestTime + road[i][2])
                continue;

            time[nextTown.number] = startTown.shortestTime + road[i][2];
            nextTown.shortestTime = startTown.shortestTime + road[i][2];
            pq.push(nextTown);
        }
    }

    for (int i = 1; i < time.size(); ++i)
        if (time[i] <= K)
            answer++;

    return answer;
}

1️⃣ 준비

struct Town {
    int number;
    int shortestTime;

    Town() {}

    Town(int _number, int _shortestTime) {
        number = _number;
        shortestTime = _shortestTime;
    }
};

struct cmp { // 우선순위큐 정렬 기준 👉 최단경로을 가진 Town 이 Pop 되게끔
    bool operator()(const Town& a, const Town& b) {
        return a.shortestTime > b.shortestTime; // 오름차순 정렬 (Min Heap)
    }
};

int solution(int N, vector<vector<int>> road, int K) {
    int answer = 0;
    const int maxTime = 20000000; // = 2,000 x 10,000(c의 최대값)
    
    vector<bool> visited(N + 1); 
    vector<int> time(N + 1, maxTime);
    priority_queue<Town, vector<Town>, cmp> pq;

마을과 마을 사이에 걸리는 “가장 짧은 배달 시간”(최단 경로)를 구할 것이다.

  • pq 👉 마을 번호(number)와 1번 마을부터 n 번 마을까지의 현재까지 구한 최단 경로(shortestTime)을 묶어서 관리하는 Town 구조체를 담는다. 우선순위 큐가 가장 먼저 pop 하는 것은 현재까지 구한 최단 경로가 가장! 짧은 Town부터 내뱉도록 항상 정렬하고 이를 유지한다.
    • 현재까지의 최단 경로가 새롭게 업데이트 될 때마다 힙.정.렬 ! ! ! 된다. 최소값이 늘 루트에 오는 힙 트리를 유지하게끔!
  • visited 👉 방문 여부 우선순위 큐에서 pop 된적이 있는 최종 방문 전적이 있는 정점
    • 다익스트라는 출발 정점으로부터 그외 모든 정점으로까지의 최단 경로를 각각 구하기 때문에 모든 정점을 순회하게 된다.
    • visited[n] 은 n번 마을을 방문한 여부를 의미한다.
    • 사실 visited는 없어도 답을 도출하는데에는 전혀 지장이 없다. 방문체크를 안해주어도 재방문 되는 정점이라면 if (time[nextTown.number] < startTown.shortestTime + road[i][2]) continue; 여기서 걸러지게 되어있기 때문이다.
      • 걸러지는 이유와 그럼에도 불구하고 visited를 사용한 이유는 아래에 후술하겠다.
  • time 👉 time[n] 은 1 번 마을로부터 n번 마을 까지의 현재까지 구한 최단 경로가 담긴다. 그러니 더 작은 값을 계속 업데이트 해 나갈 것이기 때문에 처음엔 최대값인 20,000,000 으로 모두 초기화를 해주었다.


2️⃣ 출발지

    time[1] = 0;
    pq.push(Town(1, 0));

출발지는 1 번 마을 고정이다.

  • 1 번 마을의 최단 경로(최소 배달 시간)은 0 이다.
  • 1 번 마을이 가장 처음 방문 되도록 비어있던 우선순위 큐에 삽입한다.


3️⃣ 다익스트라 : 1) 방문한다 2) 방문한 마을에 연결된 마을들의 최단 경로를 업뎃한다.

    while (!pq.empty()) { // 더 이상 큐에서 가져올게 없을 때까지, 즉 모든 정점을 순회할 때까지
        
        Town startTown = pq.top(); // startTown 은 방문한 마을
        pq.pop();

        if (visited[startTown.number]) // 이미 방문했던 마을일 수도 있다. 동일한 마을 객체가 큐에 여러개 들어 있을 수 있다. 그 이유는 아래에!
            continue;

        visited[startTown.number] = true;

        for (int i = 0; i < road.size(); ++i) {
            
            Town nextTown; // nextTown 은 다음에 방문될 수 있는 마을 (예약할 마을)
            if (road[i][0] == startTown.number)
                nextTown.number = road[i][1];
            else if (road[i][1] == startTown.number)
                nextTown.number = road[i][0];
            else
                continue;

            if (visited[nextTown.number]) // 이미 방문된 마을이라면 스킵
                continue;

            if (time[nextTown.number] < startTown.shortestTime + road[i][2]) // 최단 경로 업데이트할 필요 없다면 스킵
                continue;

            // 최단 경로 업데이트 하고 
            time[nextTown.number] = startTown.shortestTime + road[i][2];

            // 큐에 삽입 (nextTown 의 shortestTime 를 업데이트해야 힙정렬이 다시 진행됨)
            nextTown.shortestTime = startTown.shortestTime + road[i][2];
            pq.push(nextTown); // 이렇게 큐 안에 들어있는 마을 구조체의 shortestTime 값을 수정하는게 아니라
            // 아예 새로운 구조체 객체를 만들어서 큐에 새롭게 삽입하기 때문에 큐에는 동일한 마을이지만(number 같지만) 각자 계산한 최단 경로는 모두 다른 객체들이 여러개 들어있을 수 있다. (동일한 마을이지만)
        }
    }
  • 1️⃣ 방문한다. 큐에서 꺼내오자.
    • 근데 큐에서 꺼내온게 이미 방문한 마을일 가능성도 있다. 왜냐면 위에서도 언급을 했지만 큐 안에 동일한 마을 객체가 여러개가 있을 수 있기 때문이다. (마을 번호 number는 같지만 최단 경로 shortestTime 은 다른) 해당 마을의 최단 경로를 업데이트할 때 큐 안에 이미 들어있는 마을 구조체 오브젝트의 shortestTime 값을 수정할 수는 없기 때문에 (vector나 배열과 다르게 스택이나 큐는 안에 들어있는 원소에 접근할 수 없다.) 그냥 최단 경로가 업데이트 된 마을이라면 새롭게 구조체를 또 만들어서 큐에 또 넣기로 했기 때문이다.(아래 코드 참고) 그래서 동일한 번호의 마을이지만 최단 경로들은 다 다른 동일한 마을을 나타내는 객체들이 큐에 여러개가 있을 수 있고 (그만큼 최단 경로가 업데이트 되서) 그 중 가장 짧은 경로의 마을이 방문 처리 됐다면 큐 안에 들어있는 더 긴 경로들의 동일한 마을들은 제껴야 한다.
      • 최단 경로 업데이트 된 마을을 또 새롭게 우선순위 큐에 넣는 것도, 큐에서 빼냈는데 이미 방문한 마을일 수도 있는 이유도 다 큐 안에 이미 들어있는 원소에 접근하여 수정할 수 없기 때문이다.
        • ⭐ 다익스트라 알고리즘에서 우선순위 큐를 쓰는 이유기도 하다. 만약 그냥 큐를 쓴다면, 현재 큐에 경로들이 각각 다르지만 동일한 마을을 나타내는 객체가 여러개 들어있을 수 있는데 일반 큐를 쓰면 가장 짧은 경로를 가진 마을 객체부터 방문 처리 되는 것이 아닌 그냥 큐에 있은지 가장 오래된 마을 객체부터 방문하는게 되기 때문에 오답을 낳을 수 있다!! (더 짧은 경로를 가진 동일한 마을이 큐에 있음에도 이 마을은 이미 방문됐다고 처리되니 제껴질 것이니까) 반면에 우선순위 큐를 사용하면 각자 계산한 최단 경로가 다른 동일한 마을 객체들이 큐에 여러개 있더라도 가장 짧은 최단 경로를 가진 마을이 무조건 먼저 방문되니(큐에서 꺼내지니) 올바른 해가 되며 큐 안에 들어있는 그외 더 긴 경로의 동일한 마을 객체들은 아래 코드로 거르면 되는 것이다. 
          if (visited[startTown.number]) 
    continue;
        • 만약 우선순위큐 안에 있는 원소를 수정할 수 있도록 C++의 priority_queue가 그렇게 구현이 되어 있다면 큐를 써도 오답을 낳진 않을 것이다.(동일한 마을에 대한 객체를 여러개 삽입할 필요가 없어 딱 하나만 삽입하게 될 수 있기 때문이다. 그 하나만 “수정”을 하면 되니까! 그러니 큐에서 빠져나오는건 최소 경로라는게 보장됨.)
  • 2️⃣ 이번에 방문한 마을에서 갈 수 있는(연결되어 있는) 마을들의 최단경로 업데이트 하고 다음에 방문될 수 있도록 큐에 넣기
    • 아래의 경우 스킵
      • 이미 방문된 마을이라면 스킵
      • 최단 경로 업데이트할 필요 없다면, 즉 이번에 방문한 마을을 경유하는 것보다 기존에 구해놨던 최단경로가 더 짧다면 업데이트할 필요 없으니 스킵 (큐에도 이미 들어가 있음을 알 수 있다.)

🔥 방문 체크 해주는 이유 (사실 다익스트라는 방문체크 안해도 문제 없다!)

사실 다익스트라 알고리즘에서 방문체크를 안해주어도 답을 도출하는데 문제가 없다. 이미 최단 경로를 업뎃하는 과정에서 이미 방문한적이 있는 정점은 최단 경로 업뎃되지 못하고 스킵될 것이기 때문이다.

더 좋은, 더 최소의 가중치합(최단경로)를 가지는 경로를 발견했다면 최단경로를 새롭게 업데이트 해야 한다. 근데 이미 우선순위큐 안에 들어가있는 정점을 수정할 수는 없다. 큐는 배열처럼 이미 안에 들어있는 원소에 접근할 수 없기 때문이다. 따라서 어차피 가중치합만 다른 동일한 정점이 큐 안에 두개 있더라도 우선순위 큐 특성상 최소의 가중치합을 가진 정점이 먼저 빠져나오기에 동일한 정점 중 나중에 빠져나오는 정점은 업뎃 “당한”, 더 크고 안좋은 경로를 가진 정점일게 분명하다. 그러므로 어차피 이미 방문된 정점은 예약과정의 *if (time[nextTown.number] < startTown.shortestTime + road[i][2]) continue;* 코드에서 걸러지게 되어 있다.

더 자세한 예시 설명은 Chapter 6. A* 길찾기 알고리즘 구현 에 적어두었다.

그럼에도 불구하고 방문 체크 해주는 이유

  • 1️⃣ 가독성, 논리성, 역할분담
    • time은 좌표마다 현재까지의 최단 경로를 저장해두는 역할이다. if (time[nextTown.number] < startTown.shortestTime + road[i][2]) continue;로 이미 방문한 정점을 거를 수도 있지만! 그래도 역할을 분담하는게 코드를 이해하는 면에서도 좋을 것이다.
  • 2️⃣ 비용 계산이 복잡하다면 이 복잡한 비용 계산을 피할 수 있게 된다.
    • 방문 체크를 하고 미리 예약 전에 if (visited[startTown.number]) continue; 로 재방문 정점을 걸러준다면, 비용 계산을 피할 수 있다. 이정도 경로 계산은 간단한 편이지만 단순히 길이 계산 뿐만아니라 다른 여러 비용까지 합쳐지는 문제였다면 비용 계산 자체가 더 복잡해질 수도 있다. 예약 전에 이 계산 자체를 피할 수가 있으므로 성능상 더 나을 수도 있다.


4️⃣ 최소 배달 시간이 K 이하인 마을들 카운팅

    for (int i = 1; i < time.size(); ++i)
        if (time[i] <= K)
            answer++;

    return answer;

다익스트라로 최단 경로 구하는 로직이 모두 긑나고나면 time엔 최종적으로 1번 마을에서부터 i번 마을까지의 최단 경로가 담겨있게 된다.


🔥 예시

첫 번째 예제를 예로 들자면

image

  • 큐 [1], 현재까지의 최단 시간 [0,INF,INF,INF,INF]
  • 1️⃣ 1 방문 (큐에 1번 마을 밖에 없으므로 우선순위큐는 1번 마을을 pop함)
    • 1 과 연결되어 있는 마을 : 2, 4
      • 2 번 마을 예약 가능 여부
        • 1 -> 2 까지의 기존에 구한 최단 시간 : INF
        • 1 -> 2 까지 이번에 구한 시간 : 0 + 1 = 1
          • 1 < INF ⭕ 2번 마을 큐에 삽입
      • 4 번 마을 예약 가능 여부
        • 1 -> 4 까지의 기존에 구한 최단 시간 : INF
        • 1 -> 4 까지 이번에 구한 시간 : 0 + 2 = 2
          • 0 + 2 < INF ⭕ 4번 마을 큐에 삽입
    • 상황
      • 큐 [2, 4]
      • 방문 여부 [T,F,F,F,F]
      • 현재까지의 구한 1번 마을부터 걸리는 최단 시간 [0,1,INF,2,INF]
  • 2️⃣ 2 방문 (방문 안한 것 중 1번 마을과 가장 가까우므로 우선순위큐는 2번 마을을 pop함)
    • 2 과 연결되어 있는 마을 : 3, 5
      • 3 번 마을 예약 가능 여부
        • 1 -> 3 까지의 기존에 구한 최단 시간 : INF
        • 1 -> 3 까지 이번에 구한 시간(2를 거쳐서 온다면) : 1 + 3 = 4
          • 4 < INF ⭕ 3번 마을 큐에 삽입
      • 5 번 마을 예약 가능 여부
        • 1 -> 5 까지의 기존에 구한 최단 시간 : INF
        • 1 -> 5 까지 이번에 구한 시간(2를 거쳐서 온다면) : 1 + 2 = 3
          • 3 < INF ⭕ 5번 마을 큐에 삽입
    • 상황
      • 큐 [4, 3, 5]
      • 방문 여부 [T,T,F,F,F]
      • 현재까지의 구한 1번 마을부터 걸리는 최단 시간 [0,1,4,2,3]
  • 3️⃣ 4 방문 (방문 안한 것 중 1번 마을과 가장 가까우므로 우선순위큐는 4번 마을을 pop함)
    • 4 과 연결되어 있는 마을 : 1, 5
      • 1 번 마을 예약 가능 여부
        • ❌ 1 번 마을은 이미 방문 한적 있어서 안됨
      • 5 번 마을 예약 가능 여부
        • 1 -> 5 까지의 기존에 구한 최단 시간 : 3
        • 1 -> 5 까지 이번에 구한 시간(4를 거쳐서 온다면) : 2 + 2 = 4
          • 3 < 4 ❌ 5번 마을 큐에 삽입하지 않는다. 이미 1->5 번으로 가는 더 짧은 경로를 구한적이 있고 5번 마을도 이미 큐에 있음을 알 수 있다.
    • 상황
      • 큐 [3, 5]
      • 방문 여부 [T,T,F,T,F]
      • 현재까지의 구한 1번 마을부터 걸리는 최단 시간 [0,1,4,2,3]
  • 4️⃣ 3 방문 (방문 안한 것 중 1번 마을과 가장 가까우므로 우선순위큐는 3번 마을을 pop함)
    • 3 과 연결되어 있는 마을 : 2, 5
      • 2 번 마을 예약 가능 여부
        • ❌ 2 번 마을은 이미 방문 한적 있어서 안됨
      • 5 번 마을 예약 가능 여부
        • 1 -> 5 까지의 기존에 구한 최단 시간 : 3
        • 1 -> 5 까지 이번에 구한 시간(3를 거쳐서 온다면) : 4 + 1 = 5
          • 3 < 5 ❌ 5번 마을 큐에 삽입하지 않는다. 이미 1->5 번으로 가는 더 짧은 경로를 구한적이 있고 5번 마을도 이미 큐에 있음을 알 수 있다.
    • 상황
      • 큐 [5]
      • 방문 여부 [T,T,T,T,F]
      • 현재까지의 구한 1번 마을부터 걸리는 최단 시간 [0,1,4,2,3]
  • 5️⃣ 5 방문 (방문 안한 것 중 1번 마을과 가장 가까우므로 우선순위큐는 5번 마을을 pop함)
    • 5 과 연결되어 있는 마을 : 4, 2, 3
      • 4 번 마을 예약 가능 여부
        • ❌ 4 번 마을은 이미 방문 한적 있어서 안됨
      • 2 번 마을 예약 가능 여부
        • ❌ 2 번 마을은 이미 방문 한적 있어서 안됨
      • 3 번 마을 예약 가능 여부
        • ❌ 3 번 마을은 이미 방문 한적 있어서 안됨
    • 상황
      • 큐 [] 👉 큐가 비었으니 종료!!
      • 방문 여부 [T,T,T,T,T]
      • 현재까지의 구한 1번 마을부터 걸리는 최단 시간 [0,1,4,2,3]

정점 순회 순서는 1 👉2 👉 4 👉 3 👉 5 가 되었다.


🚀 최단 경로 알고리즘 참고

  • 가중치 없는 그래프에서의 최단 경로 구하기
    • BFS
      • 👉 하나의 특정 정점에서 그외 모든 정점들까지의 최단 경로 (모든 정점 순회)
      • 일반 큐 사용 (방문 안한 것 중 가장 오래된 정점부터 방문)
  • 가중치 있는 그래프에서의 최단 경로 구하기
    • 다익스트라
      • 👉 하나의 특정 정점에서 그외 모든 정점들까지의 최단 경로 (모든 정점 순회)
      • 우선순위 큐 사용 (방문 안한 것 중 가장 최단 경로를 가진 정점부터 방문)
    • 플로이드 와샬
      • 👉 모든 정점에서 그외 모든 정점들까지의 최단 경로 (정점들간의 쌍에 대한 최단 경로를 한번에 구함)
      • 3중 for문으로 한번에 구함
    • A* 길찾기
      • 👉 하나의 특정 정점에서 하나의 특정 정점까지의 최단 경로 (모든 정점을 순회하지 않음)
      • 우선순위 큐 사용 (가중치)
      • 다익스트라와 거의 똑같다. (다익스트라 응용 버전이랄까..) 목적지를 정해둔다는 것과, 다음 방문 정점을 선택할 때 지금까지 업뎃한 최단거리 뿐만 아니라 목적지까지 더 가까운 정점인지 또한 고려한다는 점 정도만 다르다.


🌜 개인 공부 기록용 블로그입니다. 오류나 틀린 부분이 있을 경우 
언제든지 댓글 혹은 메일로 지적해주시면 감사하겠습니다! 😄

맨 위로 이동하기

Programmers 카테고리 내 다른 글 보러가기

댓글 남기기

최근 글 10 개 :)