백준_16928_뱀과 사다리 게임

🙋‍♀️ 문제

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

16928번: 뱀과 사다리 게임

 

🧩 알고리즘

문제의 목적: 모든 정점 방문, 최단거리 구하기 → BFS 알고리즘

Tip) 그래프로 바꿀 수 있고 모든 가중치가 1인 문제 → BFS 알고리즘

BFS 알고리즘의 핵심은 큐에 정점을 넣을 때 방문 처리를 하는 것이다.

 

💡 아이디어

arr 배열에 2차로 이동할 칸을 저장한다. 여기서 '2차'의 의미를 설명하자면, 1차 이동이 주사위의 숫자만큼 이동하는 것이라면 2차 이동은 사다리 / 뱀이 있을 경우 또 한번 이동하는 것을 의미한다. 따라서, arr[x] = y 의 의미는 x칸에 왔을 때 2차로 이동할 칸이 y라는 것이다. 만약 사다리 / 뱀이 없는 일반칸이라면, 2차 이동이 존재하지 않으므로(=그냥 해당 칸에 머물러 있는 것이므로) 인덱스 값을 저장한다.

 

dist 배열에는 n번째 칸에 도착하는 최소 주사위 던짐 횟수를 저장한다. 또한, 이 배열을 BFS의 방문 처리에 활용한다. (-1이면 방문하지 않은 칸을 의미)

 

👩‍💻 코드

#include <iostream>
#include <queue>

using namespace std;

int arr[101];
int dist[101];

void bfs() {
	dist[1] = 0; // 1번째 칸에 도착하는 최소 주사위 던짐 횟수는 0
	queue<int> q;
	q.push(1);
	while (!q.empty()) {
		int x = q.front(); q.pop();
		for (int i = 1; i <= 6; i++) {
			int y = x + i;
			if (y > 100) continue;
			y = arr[y];
			if (dist[y] == -1) {
				dist[y] = dist[x] + 1;
				q.push(y);
			}
		}
	}
}

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int n, m;
	cin >> n >> m;
	for (int i = 1; i <= 100; i++) {
		arr[i] = i;
		dist[i] = -1;
	}
	int a, b;
	for (int i = 0; i < n; i++) { // 사다리
		cin >> a >> b;
		arr[a] = b;
	}
	for (int i = 0; i < m; i++) { // 뱀
		cin >> a >> b;
		arr[a] = b;
	}
	bfs();
	cout << dist[100] << '\n';
	return 0;
}