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

 

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

 

 

 

 

풀이)

게임 설명:
뱀과 사다리 게임은 1번 칸에서 시작해 주사위를 굴려 100번 칸에 도착하는 최소 이동 횟수를 구하는 문제입니다.
사다리를 타면 더 높은 칸으로 이동하고, 뱀을 만나면 낮은 칸으로 이동합니다.

 

풀이 흐름:

맵 초기화: 각 칸이 자기 자신을 가리키도록 설정.

 

입력 처리: 사다리와 뱀 정보를 입력받아 해당 칸의 이동 경로(map)를 업데이트.

 

BFS 탐색:

주사위를 굴려 이동 가능한 칸을 계산.

뱀 또는 사다리를 만나면 해당 칸으로 이동.

방문하지 않은 칸이면 방문 횟수를 갱신하고 큐에 추가.

 

요약)
BFS(너비 우선 탐색)를 사용하여 최소 이동 횟수를 구합니다.

큐를 활용해 이동 경로를 탐색하며, 방문한 칸은 다시 방문하지 않습니다.

 

 

코드)

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

array<int, 101>map;
array<int, 101>visited;

void bfs(int start) {
	queue<int> q;
	q.push(start);
	visited[start] = 0; 
	

	while (not q.empty()) {
		int current = q.front();
		q.pop();

		for (int i = 1; i <= 6; ++i) {
			int nx = current + i;  

			if (nx > 100) continue; // 판을 넘어갈경우

			nx = map[nx]; //뱀 사다리를 찾는다.

			if (visited[nx] == -1) {
				visited[nx] = visited[current] + 1;
				q.push(nx);
			}

		}

	}



}



int main()
{
	int n, m;
	cin >> n >> m;
	
	//배열 초기화
	for (int i = 1; i <= 100; ++i) {
		map[i] = i;
		visited[i] = -1;
	}

	//뱀 사다리 입력
	for (int i = 1; i <= n + m; ++i) {
		int x, y;
		cin >> x >> y;
		map[x] = y;
	}

	bfs(1);
	cout << visited[100]; 


}