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

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

1번부터 N번까지의 도시와 M개의 단방향 도로가 존재하고, 모든 도로의 거리는 1이다. 이 때 특정한 도시 X로부터 출발해 도달할 수 있는 모든 도시 중 최단 거리가 정확히 K인 모든 도시들의 번호를 출력하는 문제다.

 

---

문제 탐색하기

- 문제에서 구해야 하는 최종 정답은 무엇인지 탐색한 과정
- 그 정답을 구하기 위해 어떻게 코드를 구현해야 할지 고민한 과정
- 문제에 들어오는 범위를 파악하며 어떤 알고리즘을 쓸 수 있을지 고민해 가는 과정

ex. 가능한 시간 복잡도, 알고리즘 선택

입출력 제한

• 2 ≤ N ≤ 300,000
• 1 ≤ M ≤ 1,000,000
• 1 ≤ K ≤ 300,000
• 1 ≤ X ≤ N
• 1 ≤ A, B ≤ N (A와 B는 서로 다른 자연수)

 

최단 거리를 구하기 위해 BFS를 사용한다.

 

간선은 단방향으로 입력받아야 하고, '최단' 거리를 구해야 하므로 방문한 노드를 다시 방문해서는 안된다. X번 노드부터 거리가 K-1인 노드의 자식들을 정답 set에 더하고 queue에 넣지 않으면 낭비되는 시간을 줄일 수 있다.

 

---

코드 설계하기

위의 [문제 탐색하기]에서 고민한 과정을 토대로 문제 풀이에 대한 실마리를 잡고, 문제 풀이를 본격적으로 하기 전 이 문제를 풀기 위한 로드맵을 그리는 과정!

- 어떤 순서로 코드를 작성해야 할지
- 어떤 함수들을 작성해야 할지

1. N, M, K, X 입력받기
2. M개의 단방향 간선 정보 입력받기
3. X번 노드를 시작으로 BFS 함수 돌리기
   1. queue에 넣기 전
      
      1. 방문한 노드라면, 최단 거리를 구해야하므로 continue
      2. 부모 노드가 k-1의 거리에 놓여 있다면, 자식 노드는 거리가 k이므로 정답 set에 넣고 continue
   2. queue에 자식 노드를 넣으면서 진행
4. 정답 set에 있는 요소들 출력
   1. 정답 set이 비어있다면 -1 출력

 

---

시도 회차 수정 사항 (Optional)

- '틀렸습니다'를 받았다면 왜 틀렸는지 고민해보고, 어떻게 수정할 수 있는지 고민하는 과정을 작성
- 내가 세울 설계에서 어떤 부분이 틀렸는지도 함께 점검
- 한 번에 맞히면 pass해도 됨!

pass

 

---

정답 코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#define pii pair<int,int>
using namespace std;

int n,m,k,x,a,b;
bool visit[300001];
vector<int> edge[300001];
set<int> s;

void bfs(int start) {
    queue<pii> q;
    q.push({start,0});
    visit[start] = true;
    while (!q.empty()) {
        auto [a,b] = q.front();
        q.pop();
        for (auto i : edge[a]) {
            if (visit[i]) continue;
            if (b==k-1) {
                s.insert(i);
                continue;
            }
            q.push({i,b+1});
            visit[i] = true;
        }
    }
}

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

    cin >> n >> m >> k >> x;
    for (int i=0; i<m; i++) {
        cin >> a >> b;
        edge[a].push_back(b);
    }

    bfs(x);
    if (s.size()==0) cout << -1;
    else for (auto i : s) cout << i << '\n';
}