백준 18352 - 특정 거리의 도시 찾기(C++)

문제 링크입니다. https://www.acmicpc.net/problem/18352

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

BFS 혹은 다익스트라 알고리즘을 사용해 푸는 문제입니다.

X -> Y로 갈 수 있는 가중치가 1인 간선이 주어졌습니다.

이때 시작점에서 갈 수 있는 최단 거리가 K인 정점을 찾으면 되는 문제입니다.

 

가중치가 1이기 때문에 BFS를 통한 탐색 or 다익스트라 알고리즘 중 편한 것을 선택해 풀면 되는 문제입니다.

 

해당 문제를 풀기 위해 구현해야 할 것을 생각해보겠습니다.

1. 처음에 X점까지의 최단 거리를 INF로 만들어준다.

2. START에서 연결된 곳을 찾는다.

3. 연결된 곳에 저장된 최단 거리 값이 2번을 통해서 온 값보다 크다면 값을 바꿔줍니다.

4. 2번과 3번을 끝까지 반복해줍니다.

5. 최단 거리가 K인 정점을 찾습니다. 

 

1. X점까지의 최단 거리를 INF로 만들어준다.

for (int i = 1; i <= N; i++) Distance[i] = INF;

 

(2 + 3 + 4)번

void bfs(int x) {
	Distance[x] = 0;
	q.push({ 0,x });
	while (!q.empty()) {
		int X = q.front().second;
		int cost = q.front().first;
		check[X] = 1;
		q.pop();
		for (int i = 0; i < line[X].size(); i++) {
			int xx = line[X][i].first;
			int Cost = line[X][i].second;
			if (check[xx] == 0) {
				if (Distance[xx] > Distance[X] + Cost) {
					Distance[xx] = Distance[X] + Cost;
					q.push({ Distance[xx], xx });
				}
			}
		}
	}
}

간단한 BFS 코드입니다.

이전에 방문하지 않은 곳에 최단거리가 이번에 방문했을 때의 비용보다 크다면 바꿔줍니다.

 

 

자세한 것은 코드를 참고해주세요

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstring>
#include <string>
#include <queue>
#include <stack>
#include <cmath>
#define INF 987654321

using namespace std;

queue<pair<int, int>> q;
vector<pair<int, int>> line[300001];
int check[300001];
int Distance[300001];
int N, M, K, start;

void bfs(int x) {
	Distance[x] = 0;
	q.push({ 0,x });
	while (!q.empty()) {
		int X = q.front().second;
		int cost = q.front().first;
		check[X] = 1;
		q.pop();
		for (int i = 0; i < line[X].size(); i++) {
			int xx = line[X][i].first;
			int Cost = line[X][i].second;
			if (check[xx] == 0) {
				if (Distance[xx] > Distance[X] + Cost) {
					Distance[xx] = Distance[X] + Cost;
					q.push({ Distance[xx], xx });
				}
			}
		}
	}
}

void solve() {
	vector<int> point;
	for (int i = 1; i <= N; i++) Distance[i] = INF;
	bfs(start);
	for (int i = 1; i <= N; i++) {
		if (Distance[i] == K) {
			point.push_back(i);
		}
	}
	if (point.size() == 0) cout << "-1";
	else {
		sort(point.begin(), point.end());
		for (int i = 0; i < point.size(); i++) {
			cout << point[i] << "\n";
		}
	}
}

int main()
{
	cin.tie(0);
	cout.tie(0);
	cin >> N >> M >> K >> start;
	for (int i = 0; i < M; i++) {
		int x, y;
		cin >> x >> y;
		line[x].push_back({ y,1 });
	}
	solve();
	return 0;
}

 

자세한 것은 코드를 참고해주세요