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

16928번: 뱀과 사다리 게임

bfs를 이용하는 문제이다. 먼저 사다리와 뱀의 위치와 이동하는 위치를 배열에 저장해주었다. 그 후 bfs를 돌면서 위치를 이동시켜주며 카운트해주었다. 처음 100에 도달할 때 카운트를 저장한 후 출력해주었다.
처음에는 백트래킹으로 접근하여 시간 초과가 발생했다. 보드에서의 이동은 bfs를 먼저 생각해봐야겠다.

#include <iostream>
#include <queue>

using namespace std;

int N, M, res = 0;
bool visit[1001];
int ladder[101];
int snake[101];

void bfs() {
	queue<pair<int, int>> q;

	q.push({ 1,0 });
	visit[1] = true;

	while (!q.empty()) {
		int n = q.front().first;
		int count = q.front().second;

		q.pop();

		if (n == 100) {
			res = count;
			break;
		}

		for (int i = 1; i <= 6; i++) {
			int nn = n + i;

			if (nn > 100) continue;

			if (ladder[nn] != 0) {
				nn = ladder[nn];
			}
			else if (snake[nn] != 0) {
				nn = snake[nn];
			}

			if (visit[nn]) continue;
			
			q.push({ nn,count + 1 });
			visit[nn] = true;
		}
	}
}

void solution() {
	bfs();

	cout << res;
}

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

	cin >> N >> M;

	for (int i = 0; i < N; i++) {
		int a, b;
		cin >> a >> b;
		ladder[a] = b;
	}

	for (int i = 0; i < M; i++) {
		int a, b;
		cin >> a >> b;
		snake[a] = b;
	}

	solution();
	
	return 0;
}