뱀과 사다리 게임 16928 C++

이번문제는 BFS를 사용해서 푸는 문제입니다.

문제가 참신하고, 난이도도 쉬워서 재미있게 풀었습니다.

문제 바로가기
해당 문제에서 고려해야할 점은, BFS입니다.
BFS임을 어떻게 바로 알 수 있냐면, 게임판의 상태가 주어졌을 때, 100번 칸에 도착하기 위해 주사위를 굴려야 하는 횟수의 최솟값을 구해보자. 라는 조건이 있기 때문입니다.
최솟값, 또는 최단거리 이런 문제가 나오면 BFS로 푸는 것이 좋습니다.
그래야, 최단거리가 아닌 노드들은 큐에 넣지 않을 수 있기 때문입니다.

또한, Map이 10 * 10 이라고 Map을 기존에 풀던 방식처럼 int map[10][10]이렇게 놓고 풀지 않아도 되는게 함정입니다.
왜냐하면, 현재 1번 칸이라면 주사위를 굴려서 무조건 2,3,4,5,6,7로만 갈 수 있기때문에, 이차원 배열로 둬서 동서남북으로 이동하는 문제와는 다르기 때문입니다.

	cin >> LC;
	cin >> SC;
	for (int i = 1; i <= 100; i++) {
		map[i] = 100000;
	}
	for (int i = 0; i < LC + SC; i++) {
		int t1 = 0;
		int t2 = 0;
		cin >> t1;
		cin >> t2;
		um[t1] = t2;
	}

	BFS();

1차원 배열 map을 100000으로 초기화 합니다. 이렇게 하는 이유는 바로, 최솟값을 갱신하기 위해서 큰 값으로 두었습니다.

um은 unordered_map<int, int> um; 을 두어서 key-value로 사다리, 뱀을 저장하였습니다.

void BFS() {
	map[1] = 1;
	q.push({1,0});
	while (!q.empty()) {
		int c_idx = q.front().first;
		int N = q.front().second;
		q.pop();
		if (c_idx == 100 && N < result) {
			result = N;
		}
		for (int i = 1; i <= 6; i++) {
			if (1 <= c_idx + i && c_idx + i <= 100) {
				if (um[c_idx + i] > 0) {
					if (N + 1 < map[um[c_idx + i]]) {
						q.push({ um[c_idx + i],N + 1 });
						map[um[c_idx + i]] = N + 1;
					}
				}
				else {
					if (N + 1 < map[c_idx + i]) {
						q.push({ c_idx + i,N + 1 });
						map[c_idx + i] = N + 1;
					}
				}
			}
		}
	}
}

여기서는 queue의 첫번째가 현재 위치, 두번째가 주사위를 굴린 횟수입니다.

if (c_idx == 100 && N < result) {
			result = N;
		}

를 통해서 100번째 칸에 도착했을때 주사위를 굴린 최솟값인지 확인합니다.

if (1 <= c_idx + i && c_idx + i <= 100) {

해당 if문은 배열 조건 내에 있는 idx인지 확인합니다.

if (um[c_idx + i] > 0) {
					if (N + 1 < map[um[c_idx + i]]) {
						q.push({ um[c_idx + i],N + 1 });
						map[um[c_idx + i]] = N + 1;
					}
				}

unorderedmap을 사용하였으므로, c_idx + i 번째에 칸에 사다리나, 뱀이 있다면 움직이는 칸이 있으므로 양수입니다. 고로 해당 되는 칸에 가서 N+1보다 큰지 검사하여서 queue에 넣습니다.

해당 로직은 뱀이나 사다리가 아닐때도 동일합니다.

	else {
					if (N + 1 < map[c_idx + i]) {
						q.push({ c_idx + i,N + 1 });
						map[c_idx + i] = N + 1;
					}
				}

전체코드

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

int LC = 0;
int SC = 0;
int map[101];
queue<pair<int, int>>q;
unordered_map<int, int> um;
int result = 1000000;

void BFS() {
	map[1] = 1;
	q.push({1,0});
	while (!q.empty()) {
		int c_idx = q.front().first;
		int N = q.front().second;
		q.pop();
		if (c_idx == 100 && N < result) {
			result = N;
		}
		for (int i = 1; i <= 6; i++) {
			if (1 <= c_idx + i && c_idx + i <= 100) {
				if (um[c_idx + i] > 0) {
					if (N + 1 < map[um[c_idx + i]]) {
						q.push({ um[c_idx + i],N + 1 });
						map[um[c_idx + i]] = N + 1;
					}
				}
				else {
					if (N + 1 < map[c_idx + i]) {
						q.push({ c_idx + i,N + 1 });
						map[c_idx + i] = N + 1;
					}
				}
			}
		}
	}
}

int main() {
	cin >> LC;
	cin >> SC;
	for (int i = 1; i <= 100; i++) {
		map[i] = 100000;
	}
	for (int i = 0; i < LC + SC; i++) {
		int t1 = 0;
		int t2 = 0;
		cin >> t1;
		cin >> t2;
		um[t1] = t2;
	}

	BFS();
	cout << result;
}