백준 16928 (뱀과 사다리게임)

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

16928번: 뱀과 사다리 게임

해당 문제는 1 ~ 100 까지의 칸을 가진 Map 위에서 주사위 ( 1~ 6 )을 굴려 말의 위치를 옮겨가며 해당 말의 위치가 100에 도착하기 위한 최단경로를 찾는 문제이다. 따라서 BFS를 이용하여 문제를 해결하면 된다.

이때 주의해야 할 점이 BFS를 사용하여 queue에 모든 경로를 저장하게 되면 메모리 초과가 발생하게 된다 따라서 이미 방문한 경로는 다시 방문하지 않는 처리를 해주어 문제를 해결해야한다.

풀이 :

#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
#include <string>
#include <queue>

using namespace std;
struct Node{
	int idx;
	int cnt;
};

int sCnt, dCnt;
// 뱀의 위치에 해당하는 Index에 이동 하게 되는 좌표가 들어있음
int sNode[101];
// 사다리의 위치에 해당하는 Index에 이동하게 되는 좌표가 들어있음
int dNode[101];
// 메모리 초과 차단을 위해 방문경로를 check해줄 배열
int visit[101];
int map[101];

int bfs(){
	queue<Node> qu;
	qu.push({ 1, 0 });

	while (1){
		Node now = qu.front();
		for (int i = 1; i <= 6; ++i){
			if (now.idx + i > 100) continue;
			if (now.idx + i == 100) return now.cnt + 1;

			if (map[now.idx + i] == 1 || map[now.idx + i] == 2){
				// 사다리
				if (map[now.idx + i] == 1){
					// visit[] 을 사용하여 이미 방문한 경로는 qu에 push 하지 않는다
					if (visit[dNode[now.idx + i]] == 0){
						visit[dNode[now.idx + i]] = 1;
						qu.push({ dNode[now.idx + i], now.cnt + 1 });
					}
				}
				// 뱀
				else{
					// visit[] 을 사용하여 이미 방문한 경로는 qu에 push 하지 않는다
					if (visit[sNode[now.idx + i]] == 0){
						visit[sNode[now.idx + i]] = 1;
						qu.push({ sNode[now.idx + i], now.cnt + 1 });
					}
				}
			}
			else{
				// visit[] 을 사용하여 이미 방문한 경로는 qu에 push 하지 않는다
				if (visit[now.idx + i] == 0){
					visit[now.idx + i] = 1;
					qu.push({ now.idx + i, now.cnt + 1 });
				}
			}
		}
		qu.pop();
	}
}


int main(){
	//freopen_s(new FILE*, "tes.text", "r", stdin);
	cin >> dCnt >> sCnt;
	for (int i = 0; i < dCnt; ++i){
		int start, end;
		cin >> start >> end;
		dNode[start] = end;
		map[start] = 1;
	}

	for (int i = 0; i < sCnt; ++i){
		int start, end;
		cin >> start >> end;
		sNode[start] = end;
		map[start] = 2;
	}

	cout << bfs() << endl;
}