백준 18352번 특정 거리 도시 찾기 문제 풀이

문제 설명

어떤 나라에는 1번부터 N번까지의 도시와 M개의 단방향 도로가 존재한다. 모든 도로의 거리는 1이다.

이 때 특정한 도시 X로부터 출발하여 도달할 수 있는 모든 도시 중에서, 최단 거리가 정확히 K인 모든 도시들의 번호를 출력하는 프로그램을 작성하시오. 또한 출발 도시 X에서 출발 도시 X로 가는 최단 거리는 항상 0이라고 가정한다.

예를 들어 N=4, K=2, X=1일 때 다음과 같이 그래프가 구성되어 있다고 가정하자.

이 때 1번 도시에서 출발하여 도달할 수 있는 도시 중에서, 최단 거리가 2인 도시는 4번 도시 뿐이다.  2번과 3번 도시의 경우, 최단 거리가 1이기 때문에 출력하지 않는다.

문제를 보고 든 생각

• 거리가 1로 통일이므로 bfs로 간단하게 풀면 되겠다.
• 방문 체크할 배열 필요 없이 바로 거리가 갱신 되어있는 도시면 넘어가면 되겠다. (이거 때문에 83? 84? 퍼센트에서 못넘어갔다.)

풀이 간단 설명

1. X에 해당하는 번호와 거리 0을 큐에 넣었다. 그리고 X까지 거리를 -1로 설정했다. (코드를 보면 거리가 0이면 갱신하도록 했기 때문이다. 그리고 거리가 1 이상인 도시들을 찾으므로 본인을 찾을 일이 없다.)
2. X와 연결되어있는 도시들을 큐에 넣었다.
3. 큐에서 빼고 거리 갱신하는 것을 큐가 빌 때 까지 돌았다.
4. 이미 거리 정보가 입력되어 있는 도시는 넘어간다. (이때 방문체크를 할 배열이 필요가 없었다. 근데 X를 다시 돌아가는 경로가 있다면 갱신되는 것을 에러처리를 안했었다. 하나 더 배워간다.)

코드

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

#define MAX_N 300000

using namespace std;

struct strt{
  int num;
  int dist;
};

vector<int> G[MAX_N+1];
vector<int> cities;
int dist[MAX_N+1];
int N, M, K, X;

void getInput(){
  cin >> N >> M >> K >> X;
  for(int i=0; i<M; ++i){
    int v, u; cin >> v >> u;
    G[v].push_back(u);
  }
}

void setDist(){
  queue<strt> q;
  q.push({X, 0});
  dist[X] = -1;
  for(auto n : G[X]){
    q.push({n, 1});
  }

  while(!q.empty()){
    strt curr = q.front(); q.pop();
    
    if(dist[curr.num]){
      continue;
    }
    if(curr.dist == K){
      cities.push_back(curr.num);
    }
    dist[curr.num] = curr.dist;
    for(auto n : G[curr.num]){
      q.push({n, curr.dist+1});
    }
  }
}

void solve(){
  getInput();
  setDist();
  if(cities.empty()){
    cout << -1;

    return;
  }

  sort(cities.begin(), cities.end());
  for(auto city : cities){
    cout << city << "\n";
  }
}

int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  solve();

  return 0;
}