백준 16928 c++ "뱀과 사다리 게임" -PlusUltraCode-

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

 

[필자 사고]

BFS문제이다.

필자는 이 문제에서 배운점은 아래와 같다.

한번 뱀 혹은 사다리를 만나게 되면 한번만 이동할 수 있는게 아니라 계속 이동할 수 있다는 것이다.

그래서 while문을 이용하여 계속 이동할 수 있게 코드를 구성해야 된다.

또한 vistied방문 처리를 2번 설정해야 완전하게 검사가 된다.

 

이 부분을 배우게 되었다. 좋은 문제였다.

아래는 자세한 코드 해설이다.

[코드 해설]

1. 입력 처리 (Input 함수)

먼저, 보드의 크기와 뱀 및 사다리 정보를 입력받습니다.

• N개의 사다리와 M개의 뱀을 입력받습니다.
• 각각의 사다리와 뱀은 특정 칸에서 다른 칸으로 이동하는 역할을 합니다.
• 이를 map[x] = y 형태로 저장하여, x번 칸에 도착하면 y번 칸으로 이동하도록 설정합니다.

---

2. BFS 탐색 (BFS 함수)

BFS는 최단 경로 탐색에 적합한 알고리즘이며, 이 문제에서는 최소 횟수로 100번 칸에 도달하는 방법을 찾기 위해 사용됩니다.

1. 큐 초기화 및 시작 위치 설정
   • BFS 탐색을 위해 queue<Node>를 사용하여 (현재 위치, 이동 횟수)를 저장합니다.
   • 1번 칸에서 시작하며, 방문 체크 배열을 통해 중복 방문을 방지합니다.
2. 큐에서 현재 위치를 가져와 처리
   • 현재 위치와 이동 횟수를 가져와 확인합니다.
   • 만약 현재 위치가 100번 칸이면, 최소 횟수를 출력하고 종료합니다.
3. 주사위를 굴려 이동
   • 1부터 6까지 주사위를 던져 다음 칸으로 이동합니다.
   • 이동한 칸이 100을 초과하면 무시합니다.
4. 사다리 또는 뱀 확인
   • 이동한 칸에 사다리 또는 뱀이 있는 경우, 해당 위치로 이동합니다.
   • 이를 위해 map 배열을 활용하여 map[next] 값이 존재하면 계속 이동합니다.
5. 방문하지 않은 칸을 큐에 추가
   • 방문하지 않은 칸이면 큐에 추가하고, 이동 횟수를 1 증가시킵니다.
   • visited 배열을 이용해 중복 방문을 방지하여 불필요한 탐색을 줄입니다.

---

3. 게임 실행 (Game_Start 함수)

입력받은 데이터를 기반으로 BFS(1)을 실행하여 탐색을 시작합니다.

[소스 코드]

#include <iostream>
#include <queue>
#include <vector>

using namespace std;
typedef pair<int, int> Node;
vector<int> visited;
vector<int> map;
int N, M;

void Input() {
	cin >> N >> M;
	visited.resize(101);
	map.resize(102);
	for (int i = 0; i < N + M; i++) {
		int x, y;
		cin >> x >> y;
		map[x] = y;
	}
}
bool isInside(int num) {
	if (num < 0 || num>100)return false;
	return true;
}

void BFS(int start) {
	queue<Node> myQueue;
	myQueue.push({start,0});
	visited[start] = true;

	while (!myQueue.empty()) {
		int nowIdx = myQueue.front().first;
		int nowCount = myQueue.front().second;
		myQueue.pop();
		if (nowIdx == 100) {
			cout << nowCount;
			return;
		}
		for (int i = 1; i <= 6; i++) {
			int nextIdx = nowIdx + i;
			if (isInside(nextIdx)==false)continue;
			for (int k = 1; k < map.size(); k++) {
				if (visited[nextIdx])continue;
				while (map[nextIdx]!=0) {
					nextIdx = map[nextIdx];
				}

				if (visited[nextIdx] == false) {
					myQueue.push({ nextIdx,nowCount + 1 });
					visited[nextIdx] = true;
				}
			}
		}
	}
	
}

void Game_Start() {
	BFS(1);

}

int main(void) {
	Input();
	Game_Start();
}