뱀과 사다리 게임 C++ - 백준 16928

https://www.acmicpc.net/problem/16928
이 문제에 처음 접근할때에는 bfs보단 dp로도 풀릴 느낌이 들었다.
하지만 dp로 풀게되면 경우를 탐색하는 것이 복잡하게 될 수
있을 것 같아 bfs로 풀게 되었다.

먼저 주사위를 던졌을 때 i+1~i+6까지의 칸을 탐색하고, 만약 사다리,
뱀이 있다면 해당 칸으로 이동시켰다.

이때 이동시키기 전 칸까지의 경로에서 +1 혹은, i-1~i-6칸의
경로에서 +1, 이 둘중에서 최소값을 찾고 큐에 넣어주었다.

코드는 다음과 같다.

#include <bits/stdc++.h>
using namespace std;

int graph[101];
int gotile[101];
bool ifspec[101];
int N;
int M;
int pos[2];

void bfs(){
	queue<int> q;
	int start=1;
	q.push(start);
	while(!q.empty()){
		int curr=q.front();
		
		q.pop();
		for(int i=1;i<=6;i++){
			int next=curr+i;
			if(next>100){
				break;
			}
			if(ifspec[next]){
				next=gotile[next];
			}
			if(graph[next]!=0){
				if(graph[next]>graph[curr]+1){
					graph[next]=graph[curr]+1;
					q.push(next);
				}
			}
			else{
				graph[next]=graph[curr]+1;
				q.push(next);
			}
		}
	}
	
}

int main(){
	ios_base :: sync_with_stdio(false); cin.tie(NULL);
	
	cin >> N >> M;
	for(int i=0;i<N;i++){
		cin >> pos[0] >> pos[1];
		gotile[pos[0]]=pos[1];
		ifspec[pos[0]]=true;
	}
	for(int i=0;i<M;i++){
		cin >> pos[0] >> pos[1];
		gotile[pos[0]]=pos[1];
		ifspec[pos[0]]=true;
	}
	
	bfs();
	
	cout << graph[100];
}