(C++) - 백준(BOJ) 18352번 : 특정 거리의 도시 찾기

www.acmicpc.net/problem/18352

18352번: 특정 거리의 도시 찾기

기본 다익스트라 문제였습니다.

 

풀이방법

 1. 입력 및 초기화 : 단방향 그래프입니다. 도시 u,v가 있을 때 u -> v로 간다면 가중치가 1이라고 생각합니다. 또한 최단거리를 구해야 하므로 dist배열을 선언한뒤 n까지의 도시까지 나올 수 없는 큰 값으로 초기화해줍니다.

* 도시의 번호가 1부터 시작하므로 index와 헷갈리지 않도록 잘 초기화 및 저장합시다

 

 2. 다익스트라 시행 : 매번 비교하며 다음 도시로 이동할 때 거리가 가장 짧은 도시 및 가중치가 나올 수 있도록 우선순위 큐를 사용합니다. 비교 및 갱신해야할 정보는 다음 도시, 다음 도시의 가중치 이므로 한 원소가 pair로 될 수 있도록 합니다. 시작하는 도시의 거리는 0이므로 dist[start] = 0, pq에 0,start를 push해줍니다.

 

pq에 원소가 있는 동안 다음과 같은 알고리즘을 실행합니다.

 1) 변수 선언 후 저장 : 현재 도시번호 = pq.top().second, 현재 도시까지의 누적 cost = pq.top().first

 2) pop : 현재 정보를 변수 선언 후 저장했으므로 pop해줍니다.

 3) 현재 도시와 연결된 다른 모든 도시를 살펴봅니다.

     2-1) 변수를 또 선언합니다 : next = 연결된 다른 도시, nextCost = 연결된 다른 도시까지 가기 위한 cost

     2-2) 분기 : 만약 현재 도시까지 가는 cost + 다음도시로 가는 cost < 여태까지 갱신된 다음 도시까지의 cost

           dist[next] = cost + nextCost

           이 후 해당 도시를 들렀다는 의미로 pq에 push

 

* 주의해야할 점 : pq가 정렬할 때 first를 기준으로 먼저 정렬하기 때문에 정렬의 편의성을 위해 first를 도시의 가중치 second를 도시번호로 push해야합니다.

 

 3. 답 출력 : 1 ~ n번 도시까지 저장된 거리배열을 확인합니다. 그 후 k와 같은 거리가 있다면 해당 도시를 출력합니다. 그리고 flag를 세워줍니다. loop를 나온 후 !flag라면 -1를 출력해줍니다.

 

Code

#include <bits/stdc++.h>
#define INF 0x3f3f3f3f;
using namespace std;
using pii = pair<int,int>;
int n,m,k,x;

vector<pii> road[300001];
int dist[300001];

void dijkstra(int start){
    priority_queue <pii,vector<pii>,greater<pii>> pq;
    pq.push({0,start});
    dist[start] = 0;
    while(!pq.empty()){
        int cur = pq.top().second;
        int cost = pq.top().first;
        pq.pop();
        if(cost > dist[cur]) continue;
        for(int i = 0; i < road[cur].size(); i++){
            int next = road[cur][i].second;
            int nextCost = road[cur][i].first;
            if(cost + nextCost < dist[next]){
                dist[next] = cost + nextCost;
                pq.push({dist[next],next});
            }
        }
    }
}

int main(){
    cin >> n >> m >> k >> x;
    for(int i = 1; i <= n; i++) dist[i] = INF;
    for(int i = 0; i < m; i++){
        int u,v;
        cin >> u >> v;
        road[u].push_back({1,v});
    }
    dijkstra(x);
    int flag = 0;
    for(int i = 1; i <= n;i++) {
        if(dist[i] == k) {
            cout << i << '\n';
            flag = 1;
        }
    }
    if(!flag) cout << -1 << '\n';
}