[백준/C++] 뱀과 사다리 게임

문제

문제 설명

 

 

풀이

 

[문제 풀이]

 

이 문제는 특정 칸에 이동했을 때, 뱀이나 사다리가 있다면 다른 칸으로 이동할 수 있는 게 특징이다.

 

이렇게 이동을 하면서 마지막 칸인 100번 칸에 도착하면 승리하는데, 주사위를 조작해 원하는 숫자를 낼 수 있다면 100번 칸에 도달하기 위해 주사위를 가장 적게 굴리는 횟수를 구하는 문제다.

 

한번 이동할 때 마다 주사위를 굴리는 횟수가 1씩 늘어나므로, BFS로 문제를 풀면 빠르게 풀 수 있다.

 

이동 할 수 있는 곳은 현재 칸에서 1~6으로 6 곳이고, 이 6곳에 도착했을 때 뱀이나 사다리가 있다면 다른 칸으로 이동하면 된다.

 

이렇게 BFS로 문제를 구현하면 100번 칸에 처음 도달했을 때, 주사위를 굴린 횟수가 가장 적은 최소 횟수이므로 이 값을 출력하면 된다.

 

 

 

​

[아이디어 정리]

1. 어떤 칸에 사다리나 뱀이 연결되어 있다면, 방문했을 때 이동해야하는 다음 칸을 표시할 vector를 만들어 저장한다.
2. 주사위를 굴려 1~6의 범위로 이동하고, 그 칸에 사다리나 뱀이 연결되어있는지 확인한다.
3. 만약 사다리나 뱀이 없다면 그 칸에 그대로 남아있고, 사다리나 뱀이 있다면 다른 칸으로 이동한 뒤 방문표시를 한다.
4. BFS 탐색을 하다가 100번 칸을 처음 방문하게 되면 그때의 주사위를 굴린 횟수를 출력하고 코드를 종료한다.

 

 

 

Code

 

 

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

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	int N, M;
	cin >> N >> M;
	vector<int> ls(101,0);// ls[i]칸으로 이동하라는 뜻
	vector<int> visited(101, false); // 방문했는지 확인
	int a, b;
	for (int i = 0; i < N+M; i++) 
	{
		cin >> a >> b;
		ls[a] = b;
	}
	queue<pair<int, int>> q;
	pair<int, int> np = make_pair(1, 0);
	visited[1] = true;
	q.push(np);
	int nNum;
	while(!q.empty())
	{
		np = q.front();
		q.pop();
		if (np.first == 100) 
		{
			break;
		}
		for (int i = 1; i <= 6; i++) 
		{
			nNum = np.first + i;
			if (nNum<=100&&!visited[nNum]) 
			{
				visited[nNum] = true;
				if (ls[nNum] != 0) 
				{
					nNum = ls[nNum];
					visited[nNum] = true;
				}
				q.push(make_pair(nNum,np.second+1));
			}
		}
	}
	cout << np.second << endl;
	return 0;
}

 

---

쉽게 풀 수 있는 BFS 문제였다 EZ 

16928번: 뱀과 사다리 게임