[Baekjoon] 16928번: 뱀과 사다리 게임

🥅 문제

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

 

🔍 설계

주사위를 던져서 이동하는데, 이동한 칸이 사다리면, 사다리를 타고 위로 올라간다. 뱀이 있는 칸에 도착하면, 뱀을 따라서 내려가게 된다. 올라간다는 것은 현재 위치한 칸보다 번호가 큰 칸으로 이동한다는 것이고, 내려간다는 것은 현재 위치한 칸보다 번호가 작은 칸으로 이동한다는 것이다. 주의헤야할 것은 사다리나 뱀을 만나면 무조건 이용해야 하고, 한 칸에 사다리가 있거나, 뱀이 있거나, 비어있다는 것이다.

 

출발지인 1에서 목적지인 100까지 이동하기 위해, '사다리는 높은 번호의 칸으로 이동시켜 때문에 사다리만 사용하면 좋은 것 아닌가? '라는 생각을 할 수 있지만, 무조건 사다리만 이용해야만 좋은 결과가 나오리라는 보장은 없다.

 

예를 들어, {(2, 70) (75, 79) (71, 40) (41, 99)}라는 뱀과 사다리가 있을 때, 사다리만 이용한다면, 1 → (2->70) → (75->79) → 85 → 91 → 97 → 100으로 주사위를 6번 던져야 하지만, 뱀을 섞는다면, 1 → (2->70) → (71->40) → (41->99) → 100으로 4번만에 도착할 수 있다. ( → 의 개수가 주사위를 던진 횟수이다. 뱀 또는 사다리를 이용한 것은 ->로 구분하였다)

 

다시 말해서, 어떤 칸에 도착했을 때, 주사위를 던져 +1부터 +6까지 이동시켜서 모든 경우를 고려해야 하므로, BFS를 이용해야 함을 알아낼 수 있다.

---

각 칸에는 사다리가 있거나, 뱀이 있거나, 아무것도 없으므로, 일차원 벡터(link)로 연결 관계를 저장하였다. 만약, 어떤 칸에 사다리도 있고, 뱀도 있을 수 있었다면, 이차원 벡터가 필요했었을 것이다.

 

주사위를 던지는 최소 횟수를 구하기 위해, 큐에 선별해서 담기 위해, 각 칸까지 도달하기 위해 던진 주사위의 최소 횟수를 일차원 벡터(rolloing_count)에 저장한다.

 

큐에서 현재 위치(cur_loc)를 하나씩 꺼내면서, 현재 위치에서 주사위를 던진 결과를 더해 다음 위치(next_loc)를 만들고, 그 칸에 뱀이나 사다리가 있다면 뱀이나 사다리를 이용한다. 

 

만약, 이동하는 위치까지 던진 횟수가 기존에 저장한 횟수보다 작다면, 새로운 경우이므로 주사위를 던진 횟수를 갱신하고, 그 위치를 큐에 추가한다.

 

👊 풀이

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

int n, m, x, y, u, v;
vector<int> link(101);
vector<int> rolling_count(101, 1e9 + 7);

void game() {
	queue<int> q;
	q.push(1);
	rolling_count[1] = 0;
	while (!q.empty()) {
		int cur_loc = q.front();
		q.pop();
		for (int i = 1; i <= 6; i++) {
			int next_loc = cur_loc + i;
			if (next_loc > 100) {
				continue;
			}
			if (link[next_loc] != 0) {
				next_loc = link[next_loc];
			}
			if (rolling_count[next_loc] > rolling_count[cur_loc] + 1) {
				rolling_count[next_loc] = rolling_count[cur_loc] + 1;
				q.push(next_loc);
			}
		}
		
	}
}

int main(void)
{	
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		cin >> x >> y;
		link[x] = y;
	}
	for (int i = 0; i < m; i++) {
		cin >> u >> v;
		link[u] = v;
	}
	
	game();

	cout << rolling_count[100] << "\n";
	
	return 0;
}