[백준/Baekjoon] 18352 특정 거리의 도시 찾기 C++ :: Graph & Dijkstra

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

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

---

1. Logic

시작점에서 시작하여 모든 노드를 순회하면서 연결된 모든 노드까지의 최단거리를 갱신한다. 한 노드에서 모든 노드까지의 최단거리를 구하는 문제이기 때문에 다익스트라 알고리즘을 사용했다.

---

2. Code

#include <bits/stdc++.h>

using namespace std;

const int INF = 0x3f3f3f3f;

int n, m;
int k, x;

vector<int> input[300001];
int dist[300001];

void dijkstra() {
    dist[x] = 0;
    
    priority_queue<pair<int, int>> pq;
    pq.push({0, x});
    
    while(!pq.empty()) {
        int cur = pq.top().second;
        int cost = -pq.top().first;
        
        pq.pop();
        
        if(dist[cur] < cost) continue;
        
        for(int i = 0; i < input[cur].size(); i++) {
            int next = input[cur][i];
            int nCost = cost + 1;
            
            if(dist[next] > nCost) {
                dist[next] = nCost;
                pq.push({-nCost, next});
            }
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    memset(dist, INF, sizeof(dist));
    cin >> n >> m;
    cin >> k >> x;
    
    
    for(int i = 0; i < m; i++) {
        int start, end;
        cin >> start >> end;
        
        input[start].push_back(end);
    }
    
    dijkstra();
    
    bool check = false;
    for(int i = 1; i <= n; i++) {
        if(dist[i] == k) {
            check = true;
            cout << i << "\n";
        }
    }
    if(!check) {
        cout << -1;
    }
}

알고리즘 Solve 후 제가 생각한 Logic을 기록하는 개인 공부 블로그입니다.
내용 중 최적화가 가능한 부분등은 언제든지 댓글로 틀린 부분 및 피드백 주시면 공부 및 반영하겠습니다🧐

728x90