[백준 18352번] 특정 거리의 도시 찾기 (C++)

문제링크 : https://www.acmicpc.net/problem/18352

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

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define MAX 987654321
#define pii pair <int, int>

int N, M, K, X;  //도시 갯수, 도로 갯수, 거리 정보, 출발 도시 번호
int dist[300001];
vector<int>v[300001];
vector<int>result;

void dijkstra(int start)
{
    dist[start] = 0;
    queue<int>q;
    q.push(start);
    while(!q.empty())
    {
        int cur = q.front();
        q.pop();

        for(int i=0; i<v[cur].size(); i++)
        {
            int next = v[cur][i];
            if(dist[next] > dist[cur] + 1)  //모든 도로의 거리는 1
            {
                dist[next] = dist[cur] + 1;
                q.push(next);
            }
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> N >> M >> K >> X;

    fill(dist+1, dist+(N+1), MAX);  //무한대로 초기화
    
    for(int i=0; i<M; i++)
    {
        int a, b;
        cin >> a >> b;
        v[a].push_back(b);
    }

    dijkstra(X);

    for(int i=1; i<=N; i++)
    {
        if(dist[i] == K)
        {
            result.push_back(i);
        }
    }

    if(result.empty()) cout << -1;
    else
    {
        for(int i=0; i<result.size(); i++)
        {
            cout << result[i] << "\n";
        }
    }

    return 0;

}

다익스트라문제다.

원래 가중치가 따로 있어서 비용도 개별로 저장해줘야 하나, 이번 문제에서 모든 도로의 거리가 1이므로 가중치 더하는 부분에서 1만 더해주면 된다.

이렇게 거리 정보를 저장한 뒤 우리가 찾는 거리 정보가 K인 경우만 출력해주면 된다.

 

출력에 줄바꿈을 빼먹어서 여러번 틀렸다..