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

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

18352번: 특정 거리의 도시 찾기

 

이차원 벡터를 만들고, 전형적인 bfs 탐색을 하는 문제였다. 

 

시작지점과 연결되어있는 모든 정점을 방문하며, 기존에 방문하지 않은 정점이면 큐에 넣어주고 방문 표시를 한다. 

 

또한, 각 거리마다 방문 할 수 있는 정점이 다르므로, 반복문을 돌기 전 큐의 크기를 따로 저장하여 거리가 1, 2, 3 ..일 때마다 확인하며 돌 수 있도록 하였다.

 

문제의 조건 중 '최단 거리가 K인 모든 도시의 번호를 한 줄에 하나씩 오름차순으로 출력한다.' 라는 조건 때문에 정렬이 필요하다. 이때 우선순위 큐를 사용해서 정렬을 하였다. 

 

 

소스코드

#include<iostream>
#include<algorithm>
#include<queue>
#include<vector>
#define MAX 300000+1
#define endl "\n"
using namespace std;
vector<vector<int>>map(MAX);
bool visit[MAX];
int n, m, k, x;
void bfs(int start) {
	int dist = 0; // 몇만큼 갔는지
	queue<int>q;
	q.push(start);
	visit[start] = true;

	while (!q.empty()) {
		int q_size = q.size();
		for (int i = 0; i < q_size; i++) {
			int cur = q.front();
			q.pop();
			for (int j = 0; j < map[cur].size(); j++) {
				int next = map[cur][j];
				if (visit[next])continue;
				visit[next] = true;
				q.push(next);
			}
		}
		dist++;
		if (dist == k && !q.empty()) {
			priority_queue<int, vector<int>, greater<int>>pq;
			while (!q.empty()) {
				pq.push(q.front());
				q.pop();
			}
			while (!pq.empty()) {
				cout << pq.top() << endl;
				pq.pop();
			}
			return;
		}
	}
	cout << -1;
	return;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	//freopen("input.txt", "r", stdin);
	cin >> n >> m >> k >> x; // 도시, 도로, 가야할 거리, 시작 도시
	int c1; int c2;
	for (int i = 0; i < m; i++) {
		cin >> c1 >> c2;
		map[c1].push_back(c2);
	}
	bfs(x);

}