[백준 BOJ] 1753번 최단경로 (C++/cpp)

문제 설명

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

1753번: 최단경로

 

접근 방법 - 다익스트라(BFS)를 활용한 최단 경로 문제 (feat. 우선순위 큐)

백준의 1753번 문제는 너비 우선 탐색(BFS)과 깊은 연관이 있는 다익스트라 알고리즘을 활용하여 해결해야 하는 최단 경로 구하기 문제이다.

해당 문제는, 각 방향그래프의 시작점/끝점/가중치를 순차적으로 입력받을 때 시작점으로부터 각 지점마다의 최단 경로를 구하여 출력해야 하는 문제이다.

BFS로 경로를 탐색하는 일반적인 문제 이긴 하나, "각 그래프가 하나의 방향으로 정해져 있다"는 점과 "각 경로마다 가중치가 주어진다"는 점에서, 이러한 조건에 대해서 처음 문제를 풀어보는 경우라면 다소 까다로울 수도 있다. 시간초과라던가

그렇기 때문에, 당연한 이야기이겠지만 연산 횟수를 최소한으로 하면서 코드를 작성해야 할 필요가 있다.

필자와 같은 경우에는, 최단 거리부터 연산할 수 있게끔 가중치 위주로 오름차순 정렬되는 우선순위 큐를 통하여 해당 문제를 해결하였다. (기존 코드에서 큐로 바꿔서 실행하니 메모리 초과가 발생하였다.)

자세한 설명은 아래로 작성해 놓으니, 혹여나 해당 문제를 해결하는 데에 어려움을 겪고 있다면 아래의 코드와 설명을 참고해 보길 바란다.

필자는 아래의 순서대로 코드를 작성하여 문제를 해결하였다.

 

코드의 실행 순서

1) 배열 result와 <int, int> 형태의 cnt 벡터를 전역 변수로 선언해 둔다.

- 배열 result는 각 지점마다의 방문 여부와 최단 경로(정답)를 함께 저장해 두기 위해 선언한다.

- cnt 벡터는, 탐색 중인 위치에 대하여 다음 목적지 및 가중치를 함께 저장하기 위해 선언한다.

(ex) cnt[1] -> {2, 3}, {4, 5}가 있는 경우는,

      1번 -> 3번 경로의 가중치는 2이며 1번 -> 5번 경로의 가중치는 4라고 해석하게끔 하였다.

(이때, 추후에 선언하게 될 우선순위 큐 pq와 동일한 형태로 {가중치, 목적지}로 저장하게끔 하였다.)

 

2) 지점의 총 개수(n), 길의 개수(m), 그리고 시작점(start)을 입력받는다.

 

3) m의 크기만큼, 반복문을 수행하여 시작점/끝점/가중치의 쌍을 순차적으로 입력받는다.

하나씩 입력받을 때마다, 1)에 제시된 형식대로 cnt 벡터에 삽입을 수행하도록 한다.

 

4) 탐색을 시작하기 이전에, 모든 지점에 방문하지 않았다는 표시를 하기 위해 n개 지점에 대한 result의 값을 모두 -1로 저장해 둔다.

 

5) 탐색 수행을 위해, 우선순위 큐 pq를 선언한다.

이때, {현재 경로까지의 가중치, 현재 위치} 형식으로 pq에 저장할 수 있도록 <int, int> 형식으로 구성하도록 한다.

그리고 최단 경로를 수월하게 구하기 위해서, greater를 통하여 가중치를 기점으로 자동 오름차순 정렬이 되도록 한다.

(가중치를 <int, int>의 first에 두어야, greater를 통하여 자동 정렬이 된다.)

 

6) 선언을 끝내었다면, pq와 result에 대하여 시작점 설정을 한다.

- -1로 설정되어 있는 result[start]의 값을 0으로 설정한다. (실제 예제 출력에도, 시작점은 정답이 0으로 출력된다.)

- start 지점을 가장 먼저 탐색하도록, pq에 {0, start} 값을 삽입하도록 한다.

 

7) pq의 요소가 빌 때까지, 반복문을 수행하여 아래의 연산을 수행하도록 한다.

1. pq의 가장 앞에 있는 요소를 추출하여, 각 임의의 변수 초기값으로 설정하도록 한다.
   (sum_price :: 현재까지의 경로의 가중치 합 / recent :: 현재 탐색 중인 위치)
2. 메모리 초과를 방지하기 위해, pq에 대해 pop을 수행한다.
3. 현재 탐색 중인 위치(recent)를 시작점으로 갖는 길에 대해 모두 탐색을 수행한다. 
- 여기서, price는 특정 길의 가중치를 나타내며 next는 특정 길의 목적지를 나타낸다.
- 이때, 다음 지점이 아직 방문되지 않은 곳이거나(result[next] == -1) 이미 저장되어 있는 최소 가중치보다 현재 경로의 가중치가 더 작을 때(result[next] > sum_price+price), 현재 위치의 result 값을 갱신하고 pq에 현재 경로에 대한 정보를 형식에 맞게 삽입한다.

 

8) 7)의 연산이 모두 끝났다면, 현재까지 저장된 result의 n개 값을 확인해 본다.

- 만약 -1 값이 여전히 저장되어 있는 지점이라면, 문제에 제시된 대로 "INF"를 출력한다.

- -1이 아닌 다른 값이 저장되어 있는 지점이라면, 최소 가중치 값이 저장되어 있다는 뜻이기 때문에 그 값을 그대로 출력한다.

 

9) 출력을 모두 수행하였다면, 실행 종료한다.

 

필자가 하였던 실수 (연산 줄이기 수행하지 않음)

아래는 필자가 제출한 코드들 중 시간초과가 난 코드의 7) 연산 부분이다.

while (!pq.empty()) {
        int sum_price = pq.top().first;
        int recent = pq.top().second;
        // 여기서 또 비교하고 앉았음...
        if (result[recent] == -1 || result[recent] > sum_price) {
            result[recent] = sum_price;
        }
        pq.pop();

        for (int i = 0; i < cnt[recent].size(); i++) {
            int price = cnt[recent][i].first;
            int next = cnt[recent][i].second;

	// 이미 이걸 통해서 분류되어서 pq에 들어간 값인데
            if (result[next] == -1 || result[next] > sum_price + price) {
                pq.push(make_pair(sum_price + price, next));
            }
        }
    }

 

2개의 주석이 있을 텐데, 이 2개 부분이 다른 조건문 같을 수도 있다.

다만 설명처럼, pq에 들어가기 이전에 비교하였던 조건에 대해 또 같은 조건을 따지고 있는 걸 볼 수 있다.

이렇게 중복 연산을 하여 시간초과가 났었는데, 이걸 알아채지 못하였을 땐 수정에 꽤 애를 먹었다.

혹시나 도움이 될 수도 있을 듯하여 함께 기재하여 올려둔다.

반응형

 

성공한 코드

#define _CRT_SECURE_NO_WARNINGS
#pragma warning(disable: 4996)
#include <iostream>
#include <vector>
#include <utility>
#include <queue>
#define endl '\n'
using namespace std;

//백준 1753번 코드
vector<pair<int, int>> cnt[20001];
int result[20001];
int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);   cout.tie(NULL);

    int n, m, start;
    cin >> n >> m >> start;
    for (int i = 0; i < m; i++) {
        int a, b, c;
        cin >> a >> b >> c;

        cnt[a].push_back(make_pair(c, b));
    }
    // <가중치, 다음 노드 번호> 쌍

    for (int i = 1; i <= n; i++) {
        result[i] = -1;
    }
    
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    pq.push(make_pair(0, start));
    result[start] = 0;
    while (!pq.empty()) {
        int sum_price = pq.top().first;
        int recent = pq.top().second;
        pq.pop();

        for (int i = 0; i < cnt[recent].size(); i++) {
            int price = cnt[recent][i].first;
            int next = cnt[recent][i].second;

            if (result[next] == -1 || result[next] > sum_price + price) {
                // 조건문 통합하여 연산 수행
                result[next] = sum_price + price;
                pq.push(make_pair(sum_price + price, next));
            }
        }

    }

    for (int i = 1; i <= n; i++) {
        if (result[i] == -1) {
            cout << "INF" << endl;
        }
        else {
            cout << result[i] << endl;
        }
    }
}

 

제출 결과

(2023.10.22 백준 1753번 문제 제출 결과)