BaekJoon 16928번: 뱀과 사다리 게임(C++)

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

16928번: 뱀과 사다리 게임

풀이법

1) BFS와 구현이 합쳐진 문제였으며 쉽게 풀 수 있는 문제였다.

2) 1차원 배열과 방문을 표기할 배열을 선언해 주었으며, 주사위로 나올 수 있는 값인 1부터 6까지를 일일이 넣어보고, 사다리가 있는 경우 사다리를, 뱀이 있는 경우 뱀을 타도록 코딩을 진행했다.

3) 방문하지 않은 값만 새롭게 방문하도록 코딩을 진행했으며 100이 나오는 경우 결과를 출력하였다.

#include <string>
#include <iostream>
#include <cstring>
#include <vector>
#include <queue>
#include <algorithm>
#include <unordered_map>
#include <math.h>
using namespace std;

int n, m;
int arr[101];
int visited[101];
vector<pair<int, int>> ladder;
vector<pair<int, int>> snake;
void bfs()
{
	queue<pair<int, int>> q;
	q.push({ 1,0 });
	visited[1] = true;
	while (!q.empty())
	{
		int nowX = q.front().first;
		int cnt = q.front().second;
		q.pop();
		if (nowX == 100)
		{
			cout << cnt;
			return;
		}
		for (int i = 1; i <= 6; i++)
		{
			int nextX = nowX + i;
			if (!visited[nextX] && nextX <= 100)
			{
				visited[nextX] = true;
				bool check = false;
				for (int j = 0; j < ladder.size(); j++)
				{
					if (ladder[j].first == nextX)
					{
						visited[ladder[j].second] = true;
						q.push({ ladder[j].second,cnt + 1 });
						check = true;
						break;
					}
				}
				for (int j = 0; j < snake.size(); j++)
				{
					if (snake[j].first == nextX)
					{
						visited[snake[j].second] = true;
						q.push({ snake[j].second,cnt + 1 });
						check = true;
						break;
					}
				}
				if(check==false)
					q.push({ nextX,cnt + 1 });
			}
		}
	}
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n >> m;
	for (int i = 0; i < n; i++)
	{
		int a, b;cin >> a >> b;
		ladder.push_back({ a, b });
	}
	for (int i = 0; i < m; i++)
	{
		int a, b; cin >> a >> b;
		snake.push_back({ a,b });
	}
	bfs();
}