그래프의 표현 - 특정 거리의 도시 찾기

이번 문제는 가중치 없는 인접 리스트로 접근하면 되는 문제이며, 문제 풀이에 탐색을 이용해야 한다.

 

<문제>

백준 - 18352: 특정 거리의 도시 찾기

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

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

 

1번부터 N번까지의 도시와 M개의 단방향 도로가 존재하며, 모든 도로의 거리는 1이다.
이 때 특정한 도시 X로부터 출발하여 도달할 수 있는 모든 도시 중에서, 최단 거리가 정확히 K인 모든 도시들의 번호를 출력하는 코드를 작성해야한다.

 

예)
입력                출력
4 4 2 1           4
1 2
1 3
2 3
2 4
 

<문제 해결>

1. 최단 거리 k를 구하는 문제이기 때문에 BFS를 사용해야 한다.

 

2. 각 도시의 도로 거리를 나타내는 벡터가 필요하며, visited 벡터를 이용해 각 도시를 방문하면서 이동한 거리를 저장하면 된다. (ex. 거리 계산할 때 직전 도시의 거리에 1을 더하여 현재 도시의 거리로 계산하기)
 
3. 최단 거리가 k인 도시들이 여러 개가 있을 수 있기 때문에 k와 같은 거리를 가진 도시를 저장할 벡터를 생성해 준 후 오름차순으로 출력해준다. 

 

Corner case 정리)

visited 대신에 pair를 사용할 경우 메모리 초과에 유의해야 한다.

 

Approach 1. BFS 

<슈도 코드>

n_num = 도시 개수(노드 개수)
e_num = 도로 개수(간선 개수)
dist = 거리 정보
start = 출발 도시 번호

int main(){
	cin >> n_num >> e_num >> dist >> start;

	graph.resize(n_num + 1);
	visited.resize(n_num + 1, -1);
	
	for (i = 0; i < e_num; i++) {
		cin >> n1 >> n2;
		graph[n1].push_back(n2);
	}

	BFS(start);

	
	for (i = 0; i < visited.size(); i++) {
		if (visited[i] == dist) { // k와 같은 거리를 가진 도로 저장
			answer.push_back(i);
		}
	}

	if (answer.empty()) {
		cout << - 1 << endl;
	}
	else {

		sort(answer.begin(), answer.end());

		for (int i = 0; i < answer.size(); i++) {
			cout << answer[i] << endl;
		}
	}
}	
    

void BFS(int n) {
	queue <int> q;

	visited[n] += 1;
	q.push(n);
	int d = 0;

	while (!q.empty()) {

		int f = q.front();

		for (i = 0; i < graph[f].size(); i++) {

			if (visited[graph[f][i]] == -1) {
				q.push(graph[f][i]);
				visited[graph[f][i]] = visited[f] + 1; // 해당 도로의 거리 계산: 직전 도시의 거리 + 1
				
			}
			
		}
		q.pop();
	}
}

 

<전체 코드>

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

void BFS(int n);

int n_num, e_num, dist, start;
int n1, n2;

vector<vector <int>> graph;
vector <int> visited;
vector <int> answer;
static int d;
int main() {

	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> n_num >> e_num >> dist >> start;

	graph.resize(n_num + 1);
	visited.resize(n_num + 1, -1);
	
	for (int i = 0; i < e_num; i++) {
		cin >> n1 >> n2;
		graph[n1].push_back(n2);
	}

	BFS(start);

	
	for (int i = 0; i < visited.size(); i++) {
		if (visited[i] == dist) {
			answer.push_back(i);
		}
	}

	if (answer.empty()) {
		cout << - 1 << endl;
	}
	else {

		sort(answer.begin(), answer.end());

		for (int i = 0; i < answer.size(); i++) {
			cout << answer[i] << endl;
		}
	}
	
}

void BFS(int n) {
	queue <int> q;

	visited[n] += 1;
	q.push(n);
	int d = 0;

	while (!q.empty()) {

		int f = q.front();

		for (int i = 0; i < graph[f].size(); i++) {

			if (visited[graph[f][i]] == -1) {
				q.push(graph[f][i]);
				visited[graph[f][i]] = visited[f] + 1;
				
			}
			
		}
		q.pop();
	}
}