백준 18352 - 특정 거리의 도시 찾기 - BFS

문제

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

풀이전략

1. 한 도시에서 다른 도시로 가는 최단거리들을 구하면 된다. BFS로 차근차근 해결해주면 된다.

코드

#include<bits/stdc++.h>

using namespace std;

vector<int> v[300001];
int dist[300001] = {0,};
int n, m, k, x, z;

void bfs(int x){
    queue<int> q;
    q.push(x);

    while(!q.empty()){
        int nx = q.front();
        q.pop();

        for(int i=0; i<v[nx].size(); i++){
            int z = v[nx][i];
            // 다음 길로 가는 거리에 대한 정보가 없을경우 만들어준다.
            // 어차피 BFS이기 때문에 이미 만들어진 경로의 거리가 최소값이기 때문에
            // 새로운 경로와의 비교는 해줄 필요가 없다. 
            if(dist[z] == 0 && z != x){
                dist[z] = dist[nx]+1;
                q.push(z);
            }
        }
    }
}
int main() {

	cin >> n >> m >> k >> x;

	int i1, i2;
	for (int i = 0; i < m; i++) {
		cin >> i1 >> i2;
		v[i1].push_back(i2);
	}

	bfs(x);

	vector<int> answer;
	for (int i = 1; i <= n; i++) {
		if (dist[i] == k)
			answer.push_back(i);
	}
	if (answer.size() == 0)
		cout << -1 << endl;
	else {
		sort(answer.begin(), answer.end());
		for (int i = 0; i < answer.size(); i++) {
			cout << answer[i] << endl;
		}
	}
}

소감

이 문제를 왜 구현하지 못했는지는 모르겠지만... 당시 컨디션이 안좋았나보다. 결국 다른 블로그에서 가져온 것이니 한번 더 손으로 적어보도록 해야겠다.