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

문제

[C++] 백준 18352: 특정 거리의 도시 찾기 SILVER 2
https://www.acmicpc.net/problem/18352

 

---

 

접근 방법

백준 18352번은 특정 거리의 도시 찾기 문제로,
시작 도시 X에서 출발했을 때 최단 거리가 정확히 K인 도시들을 모두 출력하는 문제다.

 

모든 도로의 거리가 1로 동일하기 때문에, 이 문제는 가중치가 없는 그래프에서의 최단 거리 탐색 문제로 볼 수 있다.
이런 경우에는 BFS(너비 우선 탐색) 를 사용하면 된다.

 

그래프는 인접 리스트로 저장했다.

vector<vector<ll>> graph;

 

그리고 각 도시까지의 거리를 저장하기 위해 dist 배열을 사용했다.

vector<ll> dist;

 

초기에는 모든 도시의 거리를 -1로 설정해두고,
BFS를 하면서 처음 방문한 도시의 거리를 갱신해 나간다.

dist.resize(N + 1, -1);

 

BFS 과정에서는

• 시작 도시 X의 거리를 0으로 설정
• 인접한 도시로 갈 때마다 현재 거리 + 1로 갱신
• 이미 방문한 도시는 다시 탐색하지 않음

이렇게 하면 dist[i]에는 시작 도시 X에서 도시 i까지의 최단 거리가 저장된다.

마지막으로 전체 도시를 순회하면서 dist[i] == K 인 도시만 출력하면 된다.

 

구현 시 주의할 점

• 이 문제는 최단 거리를 구하는 문제이기 때문에 DFS로 구현하면 틀린다.
• 모든 도로의 거리가 1이므로 다익스트라가 아니라 BFS로 충분하다.
• dist 배열을 -1로 초기화해두면, 아직 방문하지 않은 도시를 쉽게 구분할 수 있다.
• 이 코드에서는 visited 배열을 별도로 두어 한 번 방문한 도시는 다시 큐에 넣지 않도록 처리했다.
• 그래프는 단방향 도로이므로 graph[a].push_back(b); 만 해야 하고,
  반대로 graph[b].push_back(a); 는 추가하면 안 된다.
• 조건을 만족하는 도시가 하나도 없을 수 있으므로,
  그런 경우에는 반드시 -1을 출력해야 한다.

 

---

 

코드

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

typedef long long ll;

ll N, M, K, X;
vector<vector<ll>> graph;
vector<ll> dist;
vector<bool> visited;

void BFS(int start)
{
	queue<ll> q;
	q.push(start);
	dist[start] = 0;
	visited[start] = true;

	while (!q.empty())
	{
		ll now = q.front();
		q.pop();

		for (ll i = 0; i < graph[now].size(); i++)
		{
			ll next = graph[now][i];

			if (!visited[next])
			{
				dist[next] = dist[now] + 1;
				q.push(next);
				visited[next] = true;
			}
		}
	}
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> N >> M >> K >> X;
	graph.resize(N + 1);
	dist.resize(N + 1, -1);
	visited.resize(N + 1, false);

	for (int i = 0; i < M; i++)
	{
		ll a = 0, b = 0;
		cin >> a >> b;

		graph[a].push_back(b);
	}
	BFS(X);

	bool flag = false;
	for (int i = 1; i <= N; i++)
	{
		if (dist[i] == K)
		{
			cout << i << '\n';
			flag = true;
		}
	}
	if (flag == false)
		cout << -1;
}