#18352 특정 거리의 도시 찾기

# 문제

# 입력 및 출력

# 풀이

bfs를 사용해서 풀었음

queue에 목적지와 depth를 pair로 저장하고 다음 턴이 되면 depth를 1증가시켜줌

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

using namespace std;
vector<int> road[300001]; 
vector<int> res; // 정답 벡터
queue<pair<int,int>> q; 
int visit[300001];

int main() {
	int n, m, k, x;
	cin >> n >> m >> k >> x;
	for (int i = 0; i < m; i++) {
		int a, b;
		cin >> a >> b;
		road[a].push_back(b);
	}
	q.push(make_pair(x, 0));
	visit[x] = 1;
	while (!q.empty()) {
		int node = q.front().first;
		int depth = q.front().second;
		q.pop();
		for (auto i : road[node]) { // 출발지가 node인 곳을 전부 확인
			if (!visit[i]) {
				if (depth + 1 == k) res.push_back(i);
				q.push(make_pair(i, depth + 1));
				visit[i] = 1;
			}
		}
	}
	sort(res.begin(), res.end()); // 오름차순 출력 위해 정렬
	if (res.empty()) {
		cout << -1 << "\n";
		return 0;
	}
	for (auto i : res) {
		cout << i << "\n";
	}
}

 

제대로 생각안하고 풀었다가 엄청 틀렸다

다익스트라 알고리즘 문제를 풀려고 했던 건데

결국엔 bfs로 풀게 됐다

다음엔 다익스트라 문제를 풀어봐야겠다