[백준/BOJ] 16928번 뱀과 사다리 게임 (C++)

www.acmicpc.net/problem/16928

16928번: 뱀과 사다리 게임

BFS 유형의 문제입니다. 뱀과 사다리 부분의 구현이 추가된 것 빼고는 숨바꼭질 2와 비슷해서 쉽게 해결했습니다.

 

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

int n, m;
int map[101];
bool visit[101];
vector<pair<int, int > > r, s;
int dx[6] = {1, 2, 3, 4, 5, 6};

int snakeOrLadder(int num) {
	for(int i = 0; i < r.size(); i++) {
		if(num == r[i].first) return r[i].second; // 사다리를 밟은 경우
	}
	
	for(int i = 0; i < s.size(); i++) {
		if(num == s[i].first) return s[i].second; // 뱀을 밟은 경우
	}
	
	return num; // 그냥 주사위 크기만큼 이동
}

int BFS() {
	queue<pair<int, int > > q;
	q.push({ 1, 0 });
	
	while(!q.empty()) {
		int now = q.front().first;
		int cnt = q.front().second;
		q.pop();
		
		visit[now] = true;
		if(now == 100) return cnt;
		
		for(int i = 0; i < 6; i++) {
			int next = now + dx[i];
			int realNext = snakeOrLadder(next);
			if(!visit[realNext] && realNext <= 100) {
				q.push({ realNext, cnt + 1 });
			}
		}
	}
	
	return 0;
}

int main(void) {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	
	cin >> n >> m;
	for(int i = 0; i < n; i++) {
		int x, y;
		cin >> x >> y;
		r.push_back({ x, y });
	}
	for(int i = 0; i < m; i++) {
		int x, y;
		cin >> x >> y;
		s.push_back({ x, y });
	}
	
	cout << BFS();
}