[ 백준 ] 5529번 - 저택 (C++)

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

5529번: 저택

 

 

[ 문제풀이 ]

 

1. 각각의 x, y 좌표에 있는 버튼들을 sero, garo 배열에 저장합니다.

 

2. 각각의 sero, garo 배열을 오름차순으로 정렬 후 인접해 있는 점끼리 간선으로 연결합니다.

 

3. 버튼을 누르면 1분이 경과하므로 버튼끼리 거리 1인 간선으로 연결해 줍니다.

 

4. 출발점을 1, 0으로 두고 노드를 추가합니다. 그리고 도착점인 M, N도 노드에 추가합니다.

 

5. 데이크스트라를 이용하여 가장 빨리 도착할 수 있는 시간을 출력합니다.

 

[ 소스코드 ]

 

#include<iostream>
#include<queue>
#include<vector>
#include<algorithm>
#include<fstream>
#define INF 0x3f3f3f3f3f3f3f3f
 
using namespace std;
 
int N, M, K;
vector<pair<int, int>> sero[100002];    //특정 x좌표의 버튼을 저장할 배열
vector<pair<int, int>> garo[100002];    //특정 y좌표의 버튼을 저장할 배열
vector<pair<int, long long>> graph[400015];        //버튼간 연결되는 간선 저장
long long dist[400015];        //각 버튼까지 도착했을 때까지 걸린 시간 저장
 
int main()
{
    //freopen("input.txt", "r", stdin);
 
    scanf("%d %d %d", &M, &N, &K);
 
    bool E = true;
 
    for (int i = 0; i <= (K+ 1) * 2 + 1; i++) {
        dist[i] = INF;
    }
 
    for (int i = 1; i <= K; i++) {
        int m, n;
        scanf("%d %d", &m, &n);
 
        sero[m].emplace_back(n, i);
        garo[n].emplace_back(m, i);
    }
    sero[1].emplace_back(0, 0);        //1,0 좌표에서 출발
 
    sero[M].emplace_back(N, K + 1);    //도착지
    garo[N].emplace_back(M, K + 1);
 
    for (int i = 1; i <= K; i++) {    //방향 변경시 버튼을 누르면 1분 경과
        graph[i * 2].emplace_back(i * 2 + 1, 1);
        graph[i * 2 + 1].emplace_back(i * 2, 1);
    }
 
    for (int i = 1; i <= N; i++) {
        sort(garo[i].begin(), garo[i].end());
    }
    for (int i = 1; i <= M; i++) {
        sort(sero[i].begin(), sero[i].end());
    }
 
    for (int i = 0; i <= N; i++) {
        for (int j = 0; j < (int)garo[i].size() - 1; j++) {
            const int dist = garo[i][j + 1].first - garo[i][j].first;
            const int u = garo[i][j + 1].second;
            const int v = garo[i][j].second;
            graph[u * 2].emplace_back(v * 2, dist);        //가로 방향 간선 연결
            graph[v * 2].emplace_back(u * 2, dist);
        }
    }
 
    for (int i = 0; i <= M; i++) {
        for (int j = 0; j < (int)sero[i].size() - 1; j++) {
            const int dist = sero[i][j + 1].first - sero[i][j].first;
            const int u = sero[i][j + 1].second;
            const int v = sero[i][j].second;
            graph[u * 2 + 1].emplace_back(v * 2 + 1, dist);    //세로 방향 간선 연결
            graph[v * 2 + 1].emplace_back(u * 2 + 1, dist);
        }
    }
 
    priority_queue<pair<long long,int>, vector<pair<long long, int>>, greater<pair<long long, int>>> pq;
 
    pq.push({-1,1});
    while (!pq.empty()) {
        const long long curDist = pq.top().first;
        const int curId = pq.top().second;
        pq.pop();
 
        if (dist[curId] < curDist) continue;
 
        for (auto &next : graph[curId]) {
            const int nextId = next.first;
            const long long nextDist = next.second;
 
            if (dist[nextId] > curDist + nextDist) {
                dist[nextId] = curDist + nextDist;
                pq.push({ dist[nextId], nextId });
            }
        }
    }
 
    if (dist[(K + 1)*2] == INF && dist[(K+1)*2+1] == INF) {
        printf("%d", -1);
    }
    else {
        printf("%lld", min(dist[(K + 1) * 2], dist[(K + 1) * 2 + 1]));
    }
}