BOJ 18352 특정 거리의 도시 찾기

이 문제의 특징은 특정 도시에서 출발하여 최단거리가 정확히 k 인 모든 도시를 출력하는것이다.

(단 k인 도시가 존재하지 않은면 -1을 출력한다.)

 

문제를 읽으면서 최단거리 키워드가 나와 BFS응용 이라는 것을 알게 되었다. 하지만 기존에 내가 풀던 BFS문제는 상,하,좌,우로 이동하는 문제를 주로 풀었다. 비슷한 로직으로 접근하여 각 노드의 간선을 인접리스트로 구현하였고, x노드를 시작으로 갈수 있는 경로를 인접리스트를 순회하면서 탐색하였다. 

 

핵심은 인접리스트 순회시 visited 표시를 하는것이다!!!

 

순회시 visited를 표시하지 않고 queue에서 pop 할때 visited를 표시해준다면 최단경로를 구할수 없다. 위의 그래프를 인접리스트를 순회할때 queue에 들어가는 값은 다음과 같다 {node, dist}

 

만약 queue를 pop 했을때 visited를 표시한다면 이후에 들어오는 queue 값은 다음과 같다

queue: {2,1},{3,1},{3,2},{4,2}   ->  이 경우 3 node의 최단거리는 1이지만 2가 출력된다.

 

하지만 인접리스트 순회시 visited를 표시하면 이후 들어오는 queue 값은 다음과 같다

queue: {2,1},{3,1},{4,2}

 

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

vector<int> adj[300001];
bool visited[300001];


void kDistNode(int dist, int startNode)
{
	vector<int> goal;
	queue<pair<int,int>> q;
	int minDist = 0;
	visited[startNode] = true;
	q.push({ startNode,minDist });

	while(!q.empty())
	{
		int node = q.front().first;
		int currentDist = q.front().second;
		q.pop();

		if(visited[node])
		{
			if(currentDist == dist)
			{
				goal.push_back(node);
			}
		}
		

		for(int i = 0; i < adj[node].size(); i++)
		{
			if(!visited[adj[node][i]])
			{
				q.push({ adj[node][i], currentDist+1 });
				visited[adj[node][i]] = true;
			}
		}
	}

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

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

	int n, m, k, x;

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

	for(int i = 1; i <= m; i++)
	{
		int a, b;
		cin >> a >> b;
		adj[a].push_back(b);
	}

	memset(visited, false, 300001 * sizeof(bool));

	kDistNode(k,x);
}