[BOJ/Gold 4] 백준 32188 Portal Game(C++)

문제 링크

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

 

문제

포탈 게임은 직선 위에서 진행되는 게임이다. 직선에는 0부터 N − 1까지의 번호가 매겨진 N개의 칸이 존재한다. 게임의 목표는 0번 칸에서 출발해 N − 1번 칸에 가능한 한 빠르게 도착하는 것이다.

이 게임에는 포탈이 총 C개 존재하며, 포탈은 레드 포탈과 블루 포탈로 총 두 종류가 있다. 각 칸에는 포탈의 시작 지점이 최대 1개 존재할 수 있다. 시작 지점이 ai번 칸에 있는 포탈을 이용하면, 해당 포탈의 끝 지점인 bi번 칸으로 이동하게 된다. 포탈은 시작 지점에서 끝 지점으로만 이동할 수 있기 때문에 동일한 포탈을 이용해 bi번 칸에서 ai번 칸으로는 이동할 수 없다.

포탈 게임에서는 N − 1번 칸에 도착하기 전까지 각 칸의 종류에 따라 아래에 제시된 행동들을 할 수 있다.

• 포탈의 시작 지점이 없는 칸: 현재 위치인 x번 칸에서 x + 1번 칸으로 1초 후 이동한다.
• 레드 포탈의 시작 지점이 있는 칸: 시작 지점이 현재 위치 x번 칸인 레드 포탈을 이용해 해당 포탈의 끝 지점으로 0초 후 이동한다.
• 블루 포탈의 시작 지점이 있는 칸: 시작 지점이 현재 위치 x번 칸인 블루 포탈을 이용해 해당 포탈의 끝 지점으로 0초 후 이동하거나 x번 칸에서 x + 1번 칸으로 1초 후 이동한다.

 

 0번 칸에서 출발해 N − 1번 칸에 도착하기 위한 최소 시간을 출력하는 프로그램을 작성해 보자.

 

입력

첫 번째 줄에 직선 위에 존재하는 칸의 개수 N, 포탈의 개수 C가 공백으로 구분되어 주어진다. (2 ≤ N ≤ 10^5; 0 ≤ C ≤ N) 

두 번째 줄부터 총 C개의 줄에 걸쳐 포탈의 정보가 한 줄에 하나씩 주어진다. 각 포탈의 정보는 정수 ti, ai, bi가 공백으로 구분되어 주어진다. ti는 i번째 포탈의 종류를 의미하며, ti = 0인 경우 레드 포탈, ti = 1인 경우 블루 포탈을 의미한다. ai, bi는 각각 i번째 포탈의 시작 지점이 위치한 칸의 번호, i번째 포탈의 끝 지점이 위치한 칸의 번호를 의미한다. (ti ∈ {0, 1}; 0 ≤ ai, bi ≤ N − 1; 0 ≤ i ≤ C − 1)

모든 포탈의 시작 지점은 중복되지 않는다. 즉, 0 ≤ i < j ≤ C − 1이면 ai ≠ aj이다.

 

출력

첫 번째 줄에 0번 칸에서 출발해 N − 1번 칸에 도착하기 위해 걸리는 최소 시간을 출력한다.

단, 어떤 방법으로 이동해도 N − 1번 칸에 도착할 수 없는 경우에는 −1을 출력한다.

 

예제 입력 1

10 2
1 2 7
0 6 3

예제 출력 1

4

예제 입력 2

14 3
0 4 2
1 5 6
0 6 8

예제 출력 2

-1

예제 입력 3

6 3
0 0 2
1 1 4
0 5 5

예제 출력 3

3

 

알고리즘 분류

• 그래프 탐색

 

풀이

각 칸마다 무슨 포탈의 시작 지점인지만 기록해 두면 BFS로 충분히 해결할 수 있다고 생각을 했으나 시간 초과가 발생을 하였다.

찾아보니 0-1 BFS를 활용해서, Queue가 아닌 Deque으로 이동 정보를 관리하면, 비용이 적은 이동 정보부터 탐색하기 때문에 시간 복잡도가 줄어든다고 하였다.

칸을 이동할 때마다, 현재 칸까지 도달했을 때 걸리는 최소 시간을 계속 갱신하고, 이동하면서 다음 칸까지 도달할 때 걸리는 최소 시간을 갱신할 수 있을 때에만 이동한다.

 

코드

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

using namespace std;
int N, C, T, A, B;
vector<pair<int, int> > Portals[MAX];
int Visited[MAX];
int Answer = INF;

void init() {
	for (int i = 1; i < MAX; i++) {
		Visited[i] = INF;
	}
}

void input() {
	cin >> N >> C;
	for (int i = 0; i < C; i++) {
		cin >> T >> A >> B;
		Portals[A].push_back(make_pair(B, T));
	}
}

void bfs() {
	deque<pair<int, int> > DQ;
	DQ.push_front(make_pair(0, 0));

	while (!DQ.empty()) {
		int NowX = DQ.front().first;
		int NowT = DQ.front().second;
		DQ.pop_front();

		if (Portals[NowX].empty()) {
			if (Visited[NowX + 1] > NowT + 1) {
				DQ.push_back(make_pair(NowX + 1, NowT + 1));
				Visited[NowX + 1] = NowT + 1;
			}
		}
		else {
			for (int i = 0; i < (int)Portals[NowX].size(); i++) {
				int NextX = Portals[NowX][i].first;
				int Type = Portals[NowX][i].second;
				if (Type == 0) {
					if (Visited[NextX] > NowT) {
						DQ.push_front(make_pair(NextX, NowT));
						Visited[NextX] = NowT;
					}
				}
				else if (Type == 1) {
					if (Visited[NextX] > NowT) {
						DQ.push_front(make_pair(NextX, NowT));
						Visited[NextX] = NowT;
					}
					if (Visited[NowX + 1] > NowT + 1) {
						DQ.push_back(make_pair(NowX + 1, NowT + 1));
						Visited[NowX + 1] = NowT + 1;
					}
				}
			}
		}
	};
}

void settings() {
	bfs();
}

void printAnswer() {
	if (Visited[N - 1] == INF) {
		cout << "-1\n";
	}
	else {
		cout << Visited[N - 1] << "\n";
	}
}

int main() {
    FASTIO

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

    return 0;
}