[백준 22868번] 산책 (small)

[백준 22868번] 산책 (small)

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

 

 출력

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

 

 

 풀이

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
int N, M, S, E;
vector<int> v[10001];
int pn[10001];
bool check[10001];

int bfs(int s, int e){
	queue<pair<int, int>> q;
	check[s] = true;
	q.push(make_pair(s, 0));
	
	while(!q.empty()){
		int a = q.front().first;
		int b = q.front().second;
		q.pop();
		
		int sz = v[a].size();
		for(int i=0;i<sz;i++){
			if(!check[v[a][i]]){
				check[v[a][i]] = true;
				pn[v[a][i]] = a;
				q.push(make_pair(v[a][i], b+1));
			}
			
			if(v[a][i] == e){
				return b+1;
			}
		}
	}
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	
	cin >> N >> M;
	for(int i=0;i<M;i++){
		int a, b; cin >> a >> b;
		v[a].push_back(b);
		v[b].push_back(a);
	}
	for(int i=1;i<=N;i++) sort(v[i].begin(), v[i].end());
	
	cin >> S >> E;
	int ans1 = bfs(S, E);
	for(int i=1;i<=N;i++) check[i] = false;
	int k = pn[E];
	while(k != 0){
		check[k] = true;
		k = pn[k];
	}
	int ans2 = bfs(E, S);
	cout << ans1 + ans2;
	return 0;
}

 일단 정점과 간선의 정보를 벡터에 넣어두고 기본적인 BFS에서 사전순으로 가장 빠른 길을 택하는 부분을 벡터를 정렬해서 BFS 돌리는 방식으로 해결했다. 길을 찾는 과정에서 결국 길을 기억해야 하기 때문에 이전 길의 정보를 담는 배열을 만들어서 S->E 처리 후에 방문체크를 해줬다. 그리고 다시 E->S로 BFS를 돌리면 S->E로 오는 길에 방문했던 정점을 무시할 수 있다. 뭔가 예외케이스가 있을 것 같아서 고민을 좀 해봤었는데 떠오르지가 않았다..

이런 경우를 생각해봤는데, 문제에서 '산책을 할 수 있는 경로가 있는 데이터만 주어진다.' 이 문구로 이런 경우는 따지지 않는 것 같다. 비슷한 문제로 산책 (Large)도 있었는데 간선의 가중치가 존재해서 다익스트라로 풀어야했는데, 다익스트라도 익숙하지 않은데다가 좀 더 복잡한 로직이 필요한 것 같아 결국 못풀었다. 플레 문제였는데 다음에 시간될 때 꼭 푼다.