[백준 18352번/c++] 특정 거리의 도시 찾기

문제

특정 도시에서 출발하여 도달할 수 있는 모든 도시 중에서 특정 최단 거리를 가지는 도시 번호를 출력한다.

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

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

조건

• 1번부터 N번까지의 도시와 M개의 단방향 도로가 존재
• 모든 도로의 거리는 1
• 특정한 도시 X로부터 출발하여 도달할 수 있는 모든 도시 중에서, 최단 거리가 정확히 K인 모든 도시들의 번호를 출력
• 출발 도시 X에서 출발 도시 X로 가는 최단 거리는 항상 0

 

입출력

입력

• 도시의 개수 N, 도로의 개수 M, 거리 정보 K, 출발 도시의 번호 X
• 두 개의 자연수 A, B
  • A번 도시에서 B번 도시로 이동하는 단방향 도로가 존재

출력

• X로부터 출발하여 도달할 수 있는 도시 중에서,
  • 최단 거리가 K인 모든 도시의 번호를 한 줄에 하나씩 오름차순으로 출력
  • 최단 거리가 K인 도시가 하나도 존재하지 않으면 -1을 출력

 

---

접근

다익스트라 알고리즘을 이용한다.

❗다익스트라 알고리즘이란 그래프에서 한 정점(노드)에서 다른 정점까지의 최단 경로를 구하는 알고리즘이다.

 

문제에서 주어진 그래프를 통해 살펴보자.

 

 

 

 

 

---

코드 구현

1. 2차원 vector 배열를 이용하여 인접리스트를 생성한다. 한 지점에서 각 노드까지의 최단거리를 저장할 1차원 vector 배열 또한 생성한다.
2. 출발 도시의 번호 X를 queue에 넣고 queue가 비어있지 않은 동안 while문을 돌린다.
   1. queue에 있는 원소를 하나씩 꺼내며, 인접리스트를 이용하여 이어져있는 노드를 for문을 통해 탐색한다.
      1. 현재 도시까지의 최단거리 + 1 < 다음 노드까지의 최단거리
         1. 최단거리 배열을 갱신해주고, queue에 노드를 넣어준다.

 

---

성공 코드(내 코드)

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

int N, M, K, X, s, e;
vector<int> city[300001];
vector<int> minDistance(300001, 300001);

void input(){
    cin >> N >> M >> K >> X;
    for(int i=0; i<M; i++){
        cin >> s >> e;
        city[s].push_back(e);
    }
}

void findMinn(){
    queue<int> q;

    minDistance[X]=0;
    q.push(X);
    while(!q.empty()){
        int current=q.front();
        q.pop();
        for(int i=0; i<city[current].size(); i++){
            int next=city[current][i];
            if(minDistance[current]+1<minDistance[next]){
                minDistance[next]=minDistance[current]+1;
                q.push(next);
            }
        }
    }
}

void output(){
    bool exist=false;

    for(int i=1; i<=N; i++){
        if(minDistance[i]==K){
            exist=true;
            cout << i << "\n";
        }
    }
    if(!exist){
        cout << -1 << "\n";
    }
}

int main(){
    ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
    // freopen("input.txt", "rt", stdin);
    
    input();
    findMinn();
    output();

    return 0;
}

---

후기

다익스트라 알고리즘을 생각해내지 못하여 무작정 구현하다가 메모리 초과와 시간 초과를 겪었던 문제이다. 다익스트라 알고리즘 개념을 잘 이해하고 있어야 해당 문제를 접근하기 쉬울 것 같다.