백준 18352 특정 거리의 도시 찾기 c++

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

using namespace std;

vector<int> answer;
int n,m,k,x,a,b;
int check[300001];
bool c[300001];
vector<int> vec[300001];

void input() {
	cin >> n >> m >> k >> x;
	for(int i=0; i<m; i++) {
		cin >> a >> b;
		vec[a].push_back(b);
	}
	
	for(int i=1; i<=300000; i++) { check[i] = 9999999; }
}

void bfs() {
	queue<pair<int,int> > q;
	q.push({x,0});
	check[x] = 0;
	
	while(!q.empty()) {
		int nx = q.front().first;
		int cnt = q.front().second;
		q.pop(); 
		check[nx] = min(check[nx],cnt);
		
		for(int i=0; i<vec[nx].size(); i++) {
			if(c[vec[nx][i]])	continue;
			c[vec[nx][i]] = true;
			q.push({vec[nx][i],cnt+1});
		}
	}
}

void solve() {
	bfs();
	for(int i=0; i<=300000; i++) {
		if(check[i] == k) { answer.push_back(i); }
	}
	
	if(answer.size() == 0) {
		cout << "-1";
		return;
	}
	
	for(int i=0; i<answer.size(); i++) {
		cout << answer[i] << endl;	
	}
}


int main() {
	input();
	solve();	
	
}

**

프로그램 흐름도

1. bfs 를 이용해 출발 도시 부터 다른 도시까지 가는 거리를 모두 갱신해준다.

2. 출발 도시부터의 최단 거리값이 K 와 같다면 answer 에 추가 한다.

3. answer 의 크기가 0이라면 -1 출력 아니라면 정렬한 후 오름차순으로 출력해준다.

 

단순 bfs 문제지만 정갑률이 낮은 이유는 아래 조건을 고려하지 않아서 그런게 아닐까

출발 도시 X에서 출발 도시 X로 가는 최단 거리는 항상 0이라고 가정한다.

 

예를들면  k = 2, 출발 도시는 1 일때 1->3 , 3->1 의 단방향 노드가 있다면 출발 도시도 포함하기 때문에 오답이 된다.