[BOJ]1753 최단경로(G4, C++)

📋 개요 

 

---

🧩 문제

https://www.acmicpc.net/problem/1753

 

📝  형식 

📥 입력	📤 출력
첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 주어진다. 셋째 줄부터 E개의 줄에 걸쳐 각 간선을 나타내는 세 개의 정수 (u, v, w)가 순서대로 주어진다. 이는 u에서 v로 가는 가중치 w인 간선이 존재한다는 뜻이다. u와 v는 서로 다르며 w는 10 이하의 자연수이다. 서로 다른 두 정점 사이에 여러 개의 간선이 존재할 수도 있음에 유의한다.	첫째 줄부터 V개의 줄에 걸쳐, i번째 줄에 i번 정점으로의 최단 경로의 경로값을 출력한다. 시작점 자신은 0으로 출력하고, 경로가 존재하지 않는 경우에는 INF를 출력하면 된다.

💡  예제

*문제 URL 참고

🥲  내 코드 및 정답코드

---

📖  해설 및 느낀점

먼저 문제에 대해서 읽어보자면, 최단거리 경로로 가는방법을 선택하는 것이다. 선택할때마다 제일 작은 가중치를 선택하면 최단 경로가 나온다.

 

최단경로 알고리즘은 여러가지 알고리즘을 활용해 output을 도출 할 수 있는데,

1. 다익스트라

2. 밸만 포드

3. 플로이드 워셜

 

위 3가지로 문제를 풀어나아갈 수 있다. 음의 가중치가 없는 그래프는 다익스트라를 활용해서 풀이가 가능하다고 한다.(다른 알고리즘은 아직 제대로 학습한적이 없다.... 이번에도 다익스트라를 처음 마주쳤다.)

 

다익스트라는 우선순위큐를 활용해서 구현할 수 있는데, pair에서 default로 정렬되는 우선순위 큐에 대해서 알아야한다.

pair를 우선순위 큐에 넣으면 어떻게 되는걸까?

 

먼저 int 형으로 우선순위 큐를 선언했을때다

#include <iostream>
#include <queue>


//priority_queue<int, 컨테이너, 비교함수(less or greter)> pq;
//defautl는 less이다.
using namespace std;
int main()
{
    priority_queue<int> pq;
    
    pq.push(1);
    pq.push(9);
    pq.push(4);
    pq.push(5);
    
    //output
    //9 5 4 1

    return 0;
}

 

그냥 int형으로 선언했을때는 보이는 것처럼 내림차순으로 우선순위큐가 정렬된다

 

공식문서를 확인해보면 default는 less기준으로 정렬된다고 되어있다. 그래서 항상 queue의 top에는 큰값이 들어온다. 문제는 int가 아닌 내가 사용하는 자료형은 vector컨테이너의 pair형이다. value가 first와 second로 두개의 value를 가지고 있다. 그렇다면 어떻게....?

#include <iostream>
#include <queue>

using namespace std;
int main()
{
    priority_queue<pair<int, int>> pq;
    
    pq.push({7,3});
    pq.push({3,7});
    pq.push({6,6});
    pq.push({3,6});
    pq.push({2,5});
    pq.push({2,4});
    
    /* output
    7,3
    6,6
    3,7
    3,6
    2,5
    2,5
    */

    return 0;
}

 

우선순위 큐에서 pair 자료구조가 어떻게 동작하는지 알아볼 수 있었다.

output을 확인해보면 first값을 기준으로 내림차순으로 정렬을 하다. first값이 같은 경우에는 second를 기준으로 내림차순을 정렬했다.

1차적으로 우선순위큐를 활용하는 방법을 배울 수 있었다. 

 

2차로는 문제에서 원하는 바는 "weight"가 작은 값을 선택하는 것이다.

우선순위 큐는 default가 less로 가장 높은 값을 먼저 둔다. 하지만 내가 최단경로 다익스트라 알고리즘을 사용하기 위해서는 오름차순 정렬이 필요하다. 방법은 3가지이다.

 

1. greater functional사용

2. operator overloading으로 compare함수 커스터마이징

2. 양수의 음수화로 절댓값순으로 내림차순 정렬

 

3가지 방법을 모두 알아보자.

첫번째는 c++의 우선순위 큐에서 사용하는 방법이다. greater functional사용해서 정렬하였다.

#include <iostream>
#include <queue>

using namespace std;
int main()
{
    priority_queue<pair<int, int>, vector<pair<int,int>> , greater<pair<int,int>>> pq;
    
    pq.push({7,3});
    pq.push({3,7});
    pq.push({6,6});
    pq.push({3,6});
    pq.push({2,5});
    pq.push({2,4});
    
    /* output
    2,4
    2,5
    3,6
    3,7
    6,6
    7,3
    */

    return 0;
}

 

 

2번째는 연산자오버로딩을 활용하였다. 결과는 모두 같은 값이 나온다.

#include <iostream>
#include <queue>

using namespace std;

struct compare{
   bool operator()(pair<int, int>&a, pair<int, int>&b) { //함수호출 연산자
                  if (a.first == b.first) return a.second > b.second;
                  else return a.first < b.first;
            }
};

int main()
{
    priority_queue<pair<int, int>, vector<pair<int,int>> , compare> pq;
    
    pq.push({7,3});
    pq.push({3,7});
    pq.push({6,6});
    pq.push({3,6});
    pq.push({2,5});
    pq.push({2,4});
    
    /* output
    2,4
    2,5
    3,6
    3,7
    6,6
    7,3
    */

    return 0;
}

 

마지막으로 세번째는 음수화를 활용하여 절대값 정렬을 의미한다. 수직선을 잘 떠올리면서 생각해보자.

#include <iostream>
#include <queue>

using namespace std;

int main()
{
    priority_queue<pair<int, int>> pq;
    
    pq.push({-7,3});
    pq.push({-3,7});
    pq.push({-6,6});
    pq.push({-3,6});
    pq.push({-2,5});
    pq.push({-2,4});
    
    while(!pq.empty()){
        cout << pq.top().first << pq.top().second << endl;
        pq.pop();
    }
    
    /* output
    -2,5
    -2,4
    -3,7
    -3,6
    -6,6
    -7,3
    */

    return 0;
}

 

그러면 우리한테 필요한건 사실 end지점까지 정렬할 필요는 없기 때문에 3번째 방법을 채택해서 활용했다. 다른 코드들을 살펴보니 많이들 그런거 같다.

 

그리고 bfs로 그래프 탐색을 진행하면서 dp배열에 1번지점 2번지점 3번 지점을 쭈욱 채워 나아가면 결과를 도출할 수 있다.

 

추가적으로,

INF는 INFINITE를 의미하는데, 어떻게 표현해야할지 고민해보고 몇개 레퍼런스가 있어서 찾아보았다.

https://stackoverflow.com/questions/8690567/setting-an-int-to-infinity-in-c

Setting an int to Infinity in C++

https://cplusplus.com/forum/beginner/111422/

calculates "inf" instead of number - C++ Forum

뭐 일단, 문제를 푸는데는 가장 큰 숫자로 정의하기만 하면 문제는 없어서 무난한걸로 선택했다. 

 

그래프 탐색이나 다익스트라 문제르 처음 마주쳐서 생각보다 답지를 봐도 오랬동안 이해를 해야했다. 왜 우선순위큐를 써야하는지? pair에서 어떻게 우선순위큐를 정렬하는지... 등등을 살펴보아야했다.