[C++] 백준 9370 - 미확인 도착지(그래프, 다익스트라, dijkstra)

0. [c++] 백준  -

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

1. 풀이

이 문제에 들어서기 앞서 우선 그래프에 대해 정리를 해보았다.

- 그래프의 종류

그래프는 크게 3가지로 분류가 된다.

1. 무방향 그래프(undirected graph)

간선에 방향이 표시되지 않은 그래프로 양방향 통행이 가능한 것을 의미한다.

2. 방향 그래프(directed graph)

간선에 방향성이 존재하는 그래프이다.

일방통행 그래프와 마찬가지로 한쪽 방향으로만 갈 수 있는 그래프이다.

3. 가중치 그래프(weighted graph)

간선에 비용이나 가중치가 할당된 그래프이다.

두 정점간의 연결 유무뿐만 아니라 연결 강도까지 나타낼 수 있어 복잡한 관계를 표현할 수 있다.

그래프를 표현하기 위해서 인접 행렬(int 배열)이나 인접 리스트(vector등을 활용해 연결된 노드를 담아주는 것)를 활용한다.

이제 이 그래프에서 최단 경로등을 파악하기 위한 방법으로는 BFS, DFS 등이 활용되는데, 그 중 특별한 알고리즘을 알아보자.

- 최소비용 신장트리(MST: minimum spanning tree)

1. kruskal의 MST 알고리즘

최소비용 신장트리(MST: minimum spanning tree)를 만드는 알고리즘이다.

방법은 다음과 같은데 간단히 요약하자면 가장 짧은 간선을 계속 추가해주는 것이다.

 1) 그래프의 모든 간선을 가중치에 따라 오름차순으로 정렬

 2) 가장 가중치가 작은 간선 e를 뽑는다.

 3) e를 넣어 신장트리에 사이클이 생기면 넣지 않고 2번으로 이동

 4) 사이클이 생기지 않으면 최소 신장 트리에 삽입

 5) n-1개의 간선이 삽입될 때 까지 2번으로 이동

시간 복잡도는 O(e loge) 이다. (이때, e는 간선의 개수)

2. Prim의 MST 알고리즘

방법은 다음과 같은데

 1) 그래프에서 시작 정점을 선택하여 초기 트리를 만든다.

 2) 현재 트리의 정점들과 인접한 정점들 중에서 간선의 가중치가 가장 작은 정점 v를 선택

 3) 이 정점 v와 이때의 간선을 트리에 추가

 4) 모든 정점이 삽입될 때 까지 2번으로 이동

간단하게 시작 지점에서 지속적으로 가장 가중치가 작은 간선을 선택해주는 것이 포인트이다.

시간 복잡도는 O(n^2)

- 최단 경로(shortest path)

1. Dijkstra의 최단 경로 알고리즘

Prim의 알고리즘과 비슷한데, 시작 노드를 잡고, 항상 가장 짧은 간선을 선택해서 범위를 점차 확장하며 시작노드와 추가된 노드 사이의 가중치를 일정 배열에 담아주는 것이다.

2. Floyd의 최단 경로 알고리즘

이 알고리즘은 모든 정점 사이의 최단 경로를 한꺼번에 찾아주는 알고리즘이다.

-------------------------------------------------------------------------------------------------

이 문제의 접근은 Dijkstra의 알고리즘을 활용하면 간단하게 해결할 수 있다.

시작 노드는 이미 주어졌고, 도착 노드는 아직 미정인 경우인 문제로 생각하고 접근하자.

우선 문제의 풀이 방법은 다음과 같다.

(1) 1번 노드를 기준으로 dijkstra를 통해 각 지점에 대한 최소거리를 찾는다.

(2) G, H노드를 기준으로 (1)번과 동일한 작업을 해준다.

(3) 1번 노드에서 출발하여, G 혹은 H 노드를 경유하는 경로의 경우라면

1 -> G -> H -> (도착지) or 1 -> H -> G -> (도착지)

      라는 2개의 경로가 나오게 된다.

이 경로의 cost의 합이 (1)번에서 구한 값과 동일하다면, 이 경로는 H, G를 경유하는 최단 경로이고,

이때의 도착지는 H-G 다리를 경로에 포함하는 최종 도착지가 된다.

이 도착지점들을 구해서 입력된 값들과 비교하는 방식으로 최종적으로 설계되었습니다.

2. 소스코드

#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
 
using namespace std;
 
const int INF = 1000000007;
const int MAX_V = 2001;
vector<pair<int, int> > V[2001];
vector<int> find_this;
 
int N, M, T;
int S, G, H;
 
vector<int> dijkstra(const int& start) {
    //각 노드로 이동하는데 필요한 시간을 저장, 처음에는 INF로 초기화
    vector<int> dist(N + 1, INF);
    //시작지점은 0으로 설정
    dist[start] = 0;
 
    priority_queue<pair<int, int> > pq;
    pq.push({ 0, start });
 
    while (!pq.empty()) {
        int cost = -pq.top().first;
        int here = pq.top().second;
        pq.pop();
        //만일 이번 코스트가 최단경로가 아니라면 패스
        if (cost > dist[here]) continue;
        for (int i = 0; i < V[here].size(); i++) {
            int there = V[here][i].first;
            int next_cost = cost + V[here][i].second;
            //다음 지점에 대해 최단경로가 갱신되는 경우
            if (next_cost < dist[there]) {
                dist[there] = next_cost;
                pq.push({ -next_cost, there });
            }
        }
    }
 
    return dist;
}
 
int main() {
    int testcase;
    cin >> testcase;
    for (int i = 0; i < testcase; i++) {
        cin >> N >> M >> T;
        cin >> S >> G >> H;
 
        //활용되는 범위에 대해 미리 초기화를 해준다.
        for (int j = 1; j <= N; j++)
            V[j].clear();
        int a, b, c;
        for (int j = 0; j < M; j++) {
            cin >> a >> b >> c;
            V[a].push_back({ b,c });
            V[b].push_back({ a,c });
        }
 
        int temp;
        //항상 초기화를 해준다.
        find_this.clear();
        for (int j = 0; j < T; j++) {
            cin >> temp;
            find_this.push_back(temp);
        }
        //미리 오름차순으로 정렬한다.
        sort(find_this.begin(), find_this.end());
 
        vector<int> root = dijkstra(S);
        vector<int> branch1 = dijkstra(G);
        vector<int> branch2 = dijkstra(H);
 
        vector<int> ret;
        for (int j = 1; j <= N; j++) {
            //시작지점에서 j번 도시까지 걸린 cost가
            //H, G점을 경유해서 돌아간 cost와 동일한 경우
            //ret에 담아 저장해준다.
            if (root[j] == root[G] + branch1[H] + branch2[j] || root[j] == root[H] + branch2[G] + branch1[j]) {
                ret.push_back(j);
            }
        }
 
        //우리가 찾기 위해 등록한 노드가 최단 노드(ret에 담겨있는 노드)중 하나인 경우
        for (int j = 0; j < find_this.size(); j++) {
            int here = find_this[j];
            for (int k = 0; k < ret.size(); k++) {
                if (here == ret[k])
                    cout << here << " ";
            }
        }
        cout << endl;
    }
 
    return 0;
}

3. 참고

질문이나 지적 있으시면 댓글로 남겨주세요~

도움 되셨으면 하트 꾹!