[BFS] 백준 16928 뱀과 사다리 게임

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

16928번: 뱀과 사다리 게임

수행시간 : 45분 / 난이도 : 실버 1

전형적인 것 같으면서도 살짝 응용이 필요한 그래프 탐색문제.

내 로직은 다음과 같다.

1. visited배열의 차원수 결정 (지도가 1차원이다)

2. BFS 함수안에서 for문을 돌때 주사위 만큼 돌아야되므로 i를 6까지로 설정해주기

3. 뱀과 사다리의 좌표를 이용해서 BFS 구현하기

 

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

int n, m;
vector<pair<int,int>> sa;
vector<pair<int,int>> baam;
bool visited[101];

void input() {
	cin >> n >> m;
	sa.resize(1000);
	baam.resize(1000);
	for (int i = 0;i < n;++i) {
		int x, y;
		cin >> x >> y;
		sa.push_back({ x,y });
	}
	for (int i = 0;i < m;++i) {
		int x, y;
		cin >> x >> y;
		baam.push_back({ x,y }); //x 이면 y가 되는거야
	}
}
void bfs(int a , int t) {
	visited[a] = true;
	queue<pair<int, int>> q;
	q.push({ a,t });
	while (!q.empty()) {
		int now = q.front().first;
		int time = q.front().second;
		q.pop();
		if (now == 100) {
			cout << time;
			return;
		}
		for (int i = 1;i <= 6;++i) { // 주사위
			int nx = now + i;
			if (nx <= 100 && visited[nx] == false) {
				for (int i = 0;i < sa.size();++i) {
					if (sa[i].first == nx) {
						nx = sa[i].second;
					}
				}
				for (int i = 0;i < baam.size();++i) {
					if (baam[i].first == nx) {
						nx = baam[i].second;
					}
				}
				visited[nx] = true;
				q.push({ nx,time + 1 });
			}
		}
	}
}

int main() {
	input();
	bfs(1, 0);
}