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

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

16928번: 뱀과 사다리 게임

[풀이]

1. bfs사용

2. 사다리나 뱀이 있는 칸은 LorS배열에 해당 칸에 도착하면 어느 칸으로 이동하는지를 저장했다.

3. visited배열을 사용하여 한 번 방문했던 칸에 대해서는 다시 탐색하지 않도록 했다.(안 하면 메모리 초과!)

 

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

struct Pos {
	int x;
	int cnt;//주사위 몇 번 굴렸는지
};

int N, M;
int LorS[101] = { 0, };//사다리, 뱀의 여부와 어디로 이어지는지
bool visited[101];

void bfs() {
	queue<Pos>q;
	q.push({ 1,0 });
	visited[1] = true;
	while (!q.empty()) {
		int x = q.front().x;
		int cnt = q.front().cnt;
		q.pop();
		if (x == 100) {
			cout << cnt << '\n';
			return;
		}
		for (int i = 1; i <= 6; i++ ) {
			int nx = x + i;
			if (nx > 100 || visited[nx])
				continue;
			//다음 칸에 사다리나 뱀이 있으면
			if (LorS[nx] != 0) {
				visited[nx] = true;
				q.push({ LorS[nx],cnt + 1 });
			}
			else {
				visited[nx] = true;
				q.push({ nx,cnt + 1 });
			}
		}
	}
}

void solution() {
	cin >> N >> M;
	int s, e;
	for (int i = 0; i < N; i++) {
		cin >> s >> e;
		LorS[s] = e;
	}
	for (int i = 0; i < M; i++) {
		cin >> s >> e;
		LorS[s] = e;
	}
	bfs();
}

int main() {
	solution();
	return 0;
}