[구름 알고리즘 먼데이 챌린지] Week7 : 3. 구름이의 여행 2

문제

구름이가 사는 구름 나라는 N개의 섬으로 이루어져 있다. 각 섬에는 1부터 N까지의 번호가 붙어 있고, 구름 나라는 사람들이 섬과 섬 사이를 편하게 이동할 수 있도록 다리를 M개 설치했다.

 

설치된 다리들은 아래의 특징들을 만족한다.

• 모든 다리는 단방향으로만 이동 가능하다.
• 다리가 잇는 두 섬은 항상 다른 섬이다.

구름이는 현재 K번 섬에 있고, 다른 섬들을 둘러본 뒤 다시 K번 섬으로 돌아오려고 한다. 그렇지만 오래 돌아다니는 것은 피곤한 일이기 때문에, 구름이는 최소한의 섬만 거치는 경로를 택할 것이다. 구름이를 도와 최소 몇 개의 섬을 거쳐서 원래 구름이가 있던 섬으로 돌아올 수 있을지 알아보자.

 

단, 구름이는 K번 섬 이외에 최소 하나 이상의 다른 섬을 방문해야 한다.

---

입력

첫째 줄에 섬의 개수 N(2 <= N <= 10,000)과 다리의 개수 M(1 <= M <= 50,000)과 구름이가 있는 섬의 번호 K(1 <= K <= N)가 공백을 두고 주어진다.

 

둘째 줄부터 M개의 줄에 걸쳐서 a, b(1 <= a, b <= N, a != b) 형태로 다리의 상태가 주어진다. 이는 a번 섬에서 b

번 섬으로 갈 수 있는 다리가 존재함을 의미한다. 동일한 시작 섬과 도착 섬을 잇는 다리가 주어지지 않는다.

 

입력에서 주어지는 모든 수는 정수이다.

---

현재 위치 K에서 다른 섬들을 거쳐 K를 돌아올 때 거치는 섬의 최소 개수를 구하는 문제이므로 최단 경로 문제와 비슷한 유형이라고 볼 수 있다.

따라서 BFS를 통해 그래프를 탐색하되 K번 섬은 중복하여 방문할 수 있다는 점에 유의하여 구현하면 쉽게 문제를 해결할 수 있다.

visited배열을 생성하여 섬의 중복 방문 여부를 확인함과 동시에 거쳐온 섬의 개수를 저장해 주었다.

K번 섬을 시작으로 연결된 다리를 따라 BFS탐색을 하며 다시 K번 섬을 방문할 때 거쳐온 섬의 개수를 출력하며 종료하도록 하였고 탐색이 끝날 때 까지 K번 섬에 다시 도달하지 못하는 경우 -1을 출력하고 종료하도록 구현하였다.

 

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

int n, m, k, a, b, visited[10001];
vector<int> edge[10001];

void bfs() {
	int cur, next;
	//K번 섬에서 시작
	visited[k] = 1;
	queue<int> q;
	q.push(k);
	while (!q.empty()) {
		cur = q.front(); q.pop();
		for (int i = 0; i < edge[cur].size(); i++) {
			next = edge[cur][i];
			//K번 섬을 제외하고 중복 방문 방지
			if (next != k && visited[next]) continue;
			//K번 섬으로 돌아온 경우 거쳐온 섬의 개수 visited[cur]을 출력
			if (next == k) { cout << visited[cur]; return;}
			visited[next] = visited[cur] + 1;
			q.push(next);
		}
	}
	cout << -1;
}

int main() {
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

	cin >> n >> m >> k;
	for (int i = 0; i < m; i++) {
		cin >> a >> b;
		edge[a].push_back(b);
	}
	bfs();
	return 0;
}