[백준 18352] 특정 거리의 도시 찾기

문제설명

주어진 노드의 수, 도로 개수, 거리정보, 출발 도시의 정보를 입력 받은 뒤,

거리 정보가 일치하는 섬을 출력시키는 문제이다

이때 섬은 단방향으로만 연결 되어있으며 , 범위는 위의 사진과 같다

알고리즘

1. 주어진 정보를 입력 받는다

2. 간선의 정보를 단방향으로 벡터에 넣는다

3. bfs 알고리즘을 사용하되 , 각 노드에 도달하는데 걸리는 값을 방문 여부에 저장한다(이때 시작점으로 돌아가는 경우는 제외)

4. 각 노드에 도달하기 위해 필요한 값을 K와 일치하는지 비교하고, 일치하면 벡터에 넣는다

5. 벡터가 비어있는 경우 -1을 출력한다

코드 

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

vector<vector<int>> road;
int N, M, K, X;
vector<int> visited;
vector<int> ans;

void bfs() {
	queue<int> q;
	q.push(X);//시작 점 queue에 넣기

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

		for (int i = 0; i < road[current].size(); i++)
		{
			int next = road[current][i];
			if (visited[next] == 0 && next !=X) { //방문한 적 없고 시작점이 아닌 경우 
				visited[next] = visited[current] + 1;//거리 값 업데이트
				q.push(next);//다음 이동지 
			}

		}
	}
	for (int i = 1; i <= N; i++)//거리 값이 찾고자 하는 거리인 경우
	{
		if (visited[i] == K)
			ans.push_back(i);
	}

}

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

	cin >> N >> M >> K >> X;

	road = vector<vector<int>>(N+1);
	visited = vector<int>(N+1);

	for (int i = 0; i < M; i++)
	{
		int x, y;
		cin >> x >> y;
		road[x].push_back(y);
	}
	bfs();
	if (ans.size() == 0) {//찾고자 하는 거리인 섬이 없는 경우
		cout << -1;
		return 0; 
	}
	
	for (int i = 0; i < ans.size(); i++)//찾고자 하는 섬 출력
		cout << ans.at(i) << '\n';
}

고찰

이번 문제는 계속 채점 결과가 83%에서 통과하지 못했다

그 이유는 시작점으로 되돌아가는 경우를 간과했기 때문이었다

주어진 예제에서 없던 경우라 빼먹고 구현했던 것이다