[C++] 백준 16928번 뱀과 사다리 게임

 

1) 문제설명

백준 Online Judge 16928번 뱀과 사다리 게임

 

2) 아이디어

주사위를 최소로 굴리는 횟수를 출력해야 하기 때문에 BFS를 사용했다.

반복문을 사용하여 주사위를 굴려서 도착한 곳이 사다리 or 뱀이 있는 곳이면 사다리 or 뱀의 목표지점으로 이동한다.

방문처리에 유의하며 BFS를 구현하면 문제없이 해결할 수 있다.

※ 서로 다른 위치의 사다리에서 같은 곳으로 이동할 수 있고 뱀을 타고 내려가도 최소 횟수로 이동할 수 있는 점을 유의한다.

3) 코드

#include<iostream>
#include<queue>
#include<deque>
#include<string.h>
#include<math.h>
#include<cmath>
#include<stack>
#include<algorithm>

using namespace std;
int arr[120];
int range[120] = { 0, };
int n, m;
int result;
queue<int> a;
int bfs(int* xrr, int* yrr) {
	a.push(1);
	arr[1] = 1;
	while (!a.empty()) {
		int x = a.front(); // 1

		a.pop();

		int dx[] = { 1,2,3,4,5,6 }; // 주사위 1~6
		for (int i = 0; i < 6; i++) {
			int nx;
			nx = x + dx[i];

			if (nx < 1 || nx > 100 || arr[nx] == 1) { // 범위를 벗어나거나 다음 도착할 곳이 이미 방문한 곳일경우
				continue; // 넘어간다
			}
			else {

				for (int j = 0; j < n + m; j++) { 
					if (nx == xrr[j]) { // 다음 도착할 곳이 뱀이나 사다리를 만날 경우
						arr[nx] = 1; // 방문 표시
						nx = yrr[j]; // 사다리를 타고 올라간다
						break;
					}
				}
				if (arr[nx] == 0) { // 사다리를 타고 올라간 곳이 방문하지 않은 곳이라면
					arr[nx] = 1; // 방문처리
					a.push(nx); 
					range[nx] = range[x] + 1;
					result = range[nx];
				}
				
			}

			if (nx == 100) {
				return result;
				break;
			}
		}

	}
}

int main() {
	int x[35], y[35];
	cin >> n >> m;

	for (int i = 0; i < n + m; i++) {
		cin >> x[i] >> y[i];
	}
	bfs(x, y);
	cout << result;
}