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

문제

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

 

주의 사항

1. 단!방!향! 도로이다. 별생각없이 하다가 출력 초과 나왔다.

2. 결과를 오름차순 출력해라!

 

풀이

BFS로 풀었다.

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

int main() 
{
	//Variable
	int N, M, K, X;
	cin >> N >> M >> K >> X;
	vector<vector<int>>graph(N + 1);
	vector<int>visit(N+1,0);
	vector<int> answer;

	//Input
	for (int i = 0; i < M; i++)
	{
		int x, y;
		cin >> x >> y;
		graph[x].push_back(y);
	}

	//First
	queue<pair<int,int>> q;
	q.push({ X,0 });
	visit[X] = 1;

	//Check
	while (!q.empty())
	{
		int now = q.front().first;
		int cnt = q.front().second;
		q.pop();

		if (cnt == K) { answer.push_back(now); continue; }

		for (int i = 0; i < graph[now].size(); i++)
		{
			int next = graph[now][i];
			if (visit[next] != 0) continue;
			visit[next] = 1;
			q.push({ graph[now][i],cnt + 1 });
		}
	}

	//Result
	sort(answer.begin(), answer.end());
	if (answer.size() == 0) { cout << -1; return 0; }
	for (int i = 0; i < answer.size()-1;i++) { cout << answer[i] << "\n"; }
	cout << answer[answer.size() - 1];
}