백준 뱀과 사다리 게임 16928 ( c++ )

 

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

16928번: 뱀과 사다리 게임

 

 

 

 

문제를 읽고 사다리만 타면 되지 않을까?라는 생각을 했었는데 좋은 사다리 위치로 가기까지 뱀의 도움도 필요하다는 것을 느끼고, 바로 BFS로 들어갔다. 

 

Queue에 향하는 위치, 움직인 횟수를 저장하는 두 개의 변수가 필요하다고 생각함.

 

원래는 pair int int를 사용해도 좋지만, 나는 구조체를 더 선호하는 편이다. 그래서 구조체를 사용해서 queue에 넣었다. 

 

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#pragma warning(disable : 4996);
int map[102] = { 0 };
bool visit[102] = { 0 };

using namespace std;
#include <queue>
struct Person {
	int place;
	int count;
};
queue<Person> ga;
void game(int x, int c) {
	Person p;
	p.place = x;
	p.count = c;
	ga.push(p);
	while (!ga.empty()) {
		int loc = ga.front().place;
		int cnt = ga.front().count;
		ga.pop();
		for (int i = 1; i <= 6; i++) {
			int nx = loc + i;
			if (nx == 100) {
				cout << cnt + 1;
				return;
			}
			else if (nx < 100) {
				while(map[nx]!=0){
					nx = map[nx];
				}
			}
			if (!visit[nx]) {
				Person p;
				p.place = nx;
				p.count = cnt + 1;
				ga.push(p);
				visit[nx] = true;
			}
		}
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	int n, m,t1,t2;
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		cin >> t1 >> t2;
		map[t1] = t2;
	}
	for (int i = 0; i < m; i++) {
		cin >> t1 >> t2;
		map[t1] = t2;
	}

	game(1, 0);
	

	return 0;
}