[BOJ/Gold 3] 백준 22868 산책 (small)(C++)

문제 링크

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

22868번: 산책 (small)

문제

코로나로 인하여 확찐자가 되버려 오늘부터 산책을 하려고 한다. 산책할 경로를 정하려고 한다.

현재 있는 곳 S에서 출발하여 S와 다른 곳인 E를 찍고 다시 S로 돌아오는 경로로 만들려고 한다. 산책을 할 때 이미 갔던 정점을 또 가기 싫어 E에서 S로 올 때 S에서 E로 간 정점을 제외한 다른 정점으로 이동하려고 한다. 또한 산책 거리가 긴 것을 싫어하여 S에서 E로 가는 짧은 거리와 E에서 S로 가는 짧은 거리를 원한다.

정점 S에서 정점 E로 이동할 때, 짧은 거리의 경로가 여러개 나올 수 있다. 그 중, 정점 S에서 정점 E로 이동한 경로를 나열했을 때, 사전순으로 가장 먼저 오는 것을 선택한다.

예를 들어, 정점 1에서 정점 2로 이동한다고 했을 때, 짧은 거리의 경로가 1 4 3 2와 1 3 4 2가 있다고 가정을 해보자. 두 개의 경로중 사전순으로 먼저 오는 것은 1 3 4 2이므로 정점 1에서 정점 2로 가는 최단 경로 중 두 번째 것을 선택한다.

이와 같이 산책 경로를 정할 때, 산책 전체 경로의 거리(S에서 E로 가는 거리 + E에서 S로 가는 거리)를 구해보자.

입력

첫 번째 줄에는 정점의 개수 N과 두 정점 사이를 잇는 도로의 개수 M이 공백으로 구분되어 주어진다.

두 번째 줄부터 M+1번째 줄까지 정점 A, B가 공백으로 구분되어 주어진다. 정점 A와 정점 B 사이의 거리는 항상 1이다. 이때, 정점 A와 정점 B는 양방향으로 이동해도 된다.

정점 A와 정점 B를 잇는 도로는 두개 이상 주어지지 않는다.

 M+2번째 줄에는 정점 S와 정점 E가 공백으로 구분되어 주어진다.

산책을 할 수 있는 경로가 있는 데이터만 주어진다.

출력

산책의 전체 경로의 길이를 출력한다.

제한

•  1≤N≤10,000
•  1≤M≤50,000
•  1≤S,E≤N

예제 입력 1

4 5
1 2
1 3
2 3
2 4
3 4
1 4

예제 출력 1

4

알고리즘 분류

• 그래프 탐색

풀이

N개의 그래프 정보를 오름차순으로 정렬한다.

그리고 S에서 E 사이의 경로의 길이를 BFS로 탐색하고(길이 1) visited[]를 이용하여 사전 순으로 가장 앞서는 경로를 제외한다.(visited[] = true)

그리고 다시 E에서 S 사이의 경로의 길이를 BFS로 탐색하고 (길이 2) S에서 E 사이의 경로의 길이와 E에서 S 사이의 경로의 길이를 합산한 길이 1 + 길이 2를 출력한다.

코드

#include <iostream>
#include <string>
#include <cmath>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <vector>
#include <algorithm>
#define FIRST cin.tie(NULL); cout.tie(NULL); ios::sync_with_stdio(false);
#define MAX 10005
#define LL long long
#define INF 2e9

using namespace std;
int N, M, S, E;
vector<int> Vec[MAX];
int Path[MAX];
int visited[MAX];
int answer = 0;

int BFS(int A, int B) {
	queue<pair<int, int> > Q;
	visited[A] = true;
	Q.push(make_pair(A, 0));

	while (!Q.empty()) {
		int CurX = Q.front().first;
		int CurCost = Q.front().second;
		Q.pop();

		for (int i = 0; i < Vec[CurX].size(); i++) {
			int nextX = Vec[CurX][i];
			if (!visited[nextX]) {
				visited[nextX] = true;
				Path[nextX] = CurX;
				Q.push(make_pair(nextX, CurCost + 1));
			}
			if (nextX == B) {
				return CurCost + 1;
			}
		}
	};

	return 0;
}

void init() {
	for (int i = 1; i <= N; i++) {
		visited[i] = false;
	}
	int K = Path[E];
	while (1) {
		visited[K] = true;
		K = Path[K];
		if (K == 0) {
			break;
		}
	};
}

int main() {
	FIRST
	cin >> N >> M;
	for (int i = 0; i < M; i++) {
		int X, Y;
		cin >> X >> Y;
		Vec[X].push_back(Y);
		Vec[Y].push_back(X);
	}
	for (int i = 1; i <= N; i++) {
		sort(Vec[i].begin(), Vec[i].end());
	}
	cin >> S >> E;
	answer += BFS(S, E);
	init();
	answer += BFS(E, S);
	cout << answer << "\n";

	return 0;
}