[BOJ/Silver 1] 백준 33254 Hurry the Hedgehog(C++)

문제 링크

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

 

문제

Hurry is a Hedgehog, who lives in the Mushroom Kingdom. He is on a mission to save Princess Plum from the evil Donkey Kong. In order to get to the Princess, Hurry must run through a hyperspace network of roads. These roads are dangerous and for every road that he walks between two intersections, he is getting attacked by Space Invaders. Luckily, at some intersections, there is a Super Mushroom that will restore Hurry's health.

Can you find the shortest path through the network of roads, such that you can eat a Super Mushroom at each intersection?

 

입력

The intersections are numbered between 1 and n, inclusive. \ Hurry will need to start at intersection 1 and run to intersection n. \ The input is structured as follows:

• One line with three integers: 1 ≤ n ≤ 10^5, the number of intersections; 0 ≤ m ≤ 10^6, the number of roads; and 1 ≤ s ≤ n, the number of Super Mushrooms.
• One line with max(0, s − 2) integers: the indices of the intersections that have a Super Mushroom (intersections 1 and n will always have a Super Mushroom and are not in this list).
•  m lines with two integers each, indicating that there is a road between the two intersections with these indices.

 

출력

One line containing one integer, which is the number of intersections in the path that Hurry will have to run.

 

예제 입력 1

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

예제 출력 1

5

예제 입력 2

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

예제 출력 2

3

 

알고리즘 분류

• 그래프 탐색

 

풀이

반드시 슈퍼 버섯이 있는 교차점으로만 이동 가능하다.

 

코드

#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <algorithm>
#define MAX 100001
#define FASTIO cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);

using namespace std;
int N, M, S, A, U, V;
bool Mushroom[MAX];
vector<int> Edges[MAX];
bool Visited[MAX];
int Answer;

void input() {
	cin >> N >> M >> S;
	Mushroom[1] = true;
	Mushroom[N] = true;
	for (int i = 0; i < max(0, S - 2); i++) {
		cin >> A;
		Mushroom[A] = true;
	}
	for (int i = 0; i < M; i++) {
		cin >> U >> V;
		Edges[U].push_back(V);
		Edges[V].push_back(U);
	}
}

void bfs() {
	queue<pair<int, int> > Q;
	Visited[1] = true;
	Q.push(make_pair(1, 1));

	while (!Q.empty()) {
		int NowX = Q.front().first;
		int NowC = Q.front().second;
		Q.pop();

		if (NowX == N) {
			Answer = NowC;
			return;
		}

		for (int i = 0; i < (int)Edges[NowX].size(); i++) {
			int NextX = Edges[NowX][i];
			if (Mushroom[NextX] && !Visited[NextX]) {
				Q.push(make_pair(NextX, NowC + 1));
				Visited[NextX] = true;
			}
		}
	};
}

void settings() {
	bfs();
}

void printAnswer() {
	cout << Answer << "\n";
}

int main() {
	FASTIO

	input();
	settings();
	printAnswer();

	return 0;
}