[BOJ_C++] 16928번 : 뱀과 사다리 게임

code

#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h> 

using namespace std;
int moveN[101];
int check[101];

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

	memset(check, 0, sizeof(check));
	for (int i = 1; i < 101; i++) {
		moveN[i] = i;
	}

	int n, m; cin >> n >> m;
	int temp1, temp2;
	for (int i = 0; i < n + m; i++) {
		cin >> temp1 >> temp2;
		moveN[temp1] = temp2;
	}

	check[1] = 0;
	queue<int> q;
	q.push(1);
	while (!q.empty()) {
		temp1 = q.front();
		q.pop();
		for (int i = 1; i <= 6; i++) {
			temp2 = temp1 + i;
			if (temp2 > 100) continue;
			temp2 = moveN[temp2];
			if (!check[temp2]) {
				check[temp2] = check[temp1] + 1;
				q.push(temp2);
			}
		}
	}

	cout << check[100];

	return 0;
}

• 처음 문제에 접근할 때 사다리만을 이용해서 문제를 해결하는 것이 가장 빠른 방법이라고 생각했다. 그러나 사실 사다리와 뱀 모두 다른 곳으로 이동할 수 있다는 점을 사용하여 풀이하는 문제였던 것 같다.
• 방문을 확인하기 위한 배열 check와 움직일 수 있는 곳을 담아두는 배열 moveN을 생성하였다. moveN의 경우 각 인덱스 번호로 초기화 하였는데 이유는 사다리나 뱀이 아닌 경우 해당 칸에 머무르면 되기 때문이다.
• 입력을 받으며 뱀과 사다리의 정보를 받았고, check[1]은 시작이므로 이동 카운트로 0을 넣어 주었다.
• bfs를 통하여 문제를 해결할 것이므로 queue를 생성하였고 처음 시작위치인 1을 넣어 주었다.
• 주사위의 가능 범위인 1부터 6을 탐색하며 100이 넘어가지 않도록 주의하고, 이동을 표시하는 temp2에 moveN[temp2]값을 넣어 이동하는 칸을 담아두었다. 만약 한 번도 방문한 적없는 곳(이동 카운트 0)이라면 해당 인덱스에 직전 이동카운트 + 1을 한 값을 넣어주고 다음에 연결될 곳을 탐색하기 위해 q에 넣어준다.
• 마지막으로 check[100] 도착위치에 있는 이동카운트를 출력하고 프로그램을 종료한다.

결과