백준 16928. 뱀과 사다리 게임

알고리즘 중급 문제 중 611 - BFS(연습)

뱀과 사다리 게임

1. 간단 설명

---

게임 규칙

• 정육면체 주사위 사용
• 게임의 크기는 10x10, 총 100칸
• 보드에는 1부터 100까지 수가 하나씩 적혀있음
• 플레이어는 주사위를 굴려 나온 수 만큼 이동
  • i에 있고 4가 나왔다면, i+4칸으로 이동
• 100을 넘었다면 이동할 수 없음. <- 움직일 수 없는건가?
• 도착한 칸이 사다리라면, 사다리를 타고 위로 올라감
• 뱀이 있는 칸에 도착하면, 뱀을 따라 내려감
• 사다리를 이동한 칸의 번호는, 원래 있던 칸의 번호보다 크고, 뱀을 이용해 이동한 칸의 번호는, 원래 있던 칸보다 작다
  • 즉 사다리는 위로 빠르게 이동, 뱀은 아래로 미끄러지는것
• 게임의 목표는 1에서 100번째 칸에 도착하는 것

게임판의 상태가 주어졌을 때, 100번 칸에 도착하기 위해서 주사위를 굴려야하는 횟수의 최소값 구하기

입력

• 사다리수 N과, 뱀의 수 M이 주어짐
• 둘째줄 부터 N개의 사다리 정보 x, y가 주어짐. x번에 도착하면, y번으로 이동한다
• 다음 M개 줄에는 뱀의 정보를 의미하는 u, v가 주어짐. u번에 도착하면, v 번으로 떨어진다
• 1번과 100번은 사다리 또는 뱀이 될 수 없음.
• 모든칸은 최대 하나의 사다리 또는 뱀을 가질 수 있음
• 동시에 두가지를 가지는 경우는 없음
• 항상 100번 칸에 도착할 수 있는 입력만 주어짐

출력

100번 칸에 도착하기 위해 주사위를 최소 몇번 굴려야 하는가?

2. 예시

예제1)

3 7
32 62
42 68
12 98
95 13
97 25
93 37
79 27
75 19
49 47
67 17

5를 굴려 6으로 이동 -> 6에서 12로 이동(12에서 사다리타고 98로 이동) -> 98에서 100으로 이동

3. 알고리즘

---

BFS를 통해서, 최대한 빠르게 100에 도달하는 경우를 찾는다

DFS로 하면 당연히 시간 초과가 난다

1. 사다리 개수 N, 뱀의 개수 M 입력받기
2. 사다리 정보, 뱀 정보 입력받기
3. BFS시작. 시작지점 1을 넣음
	3-1. 큐에서 맨 앞 노드를 꺼냄
	3-2. 도착지점(100)이라면 지금까지 굴린 회수 출력
	3-3. 현재 지점에서 갈수있는 경로 탐색
		3-3-1. 주사위 눈 만큼 더한 좌표를 계산
		3-3-2. 이 좌표에 사다리 혹은 뱀이 있는지 체크, 사다리나 뱀이 있다면 연결된 번호를 대신 넣음
		3-3-3. 없다면 그대로 넣는다

필요 변수

• 사다리와 뱀의 개수 int N, M (1 ≤ N, M ≤ 15)
• 어디로 이어질지 기록할 int teleport[101]
  • 사다리 혹은 뱀이 없는 번호는 자기자신과 연결되도록 설정
  • 사다리 혹은 뱀이 있는 번호는 다른 번호로 연결
• 이미 방문했다면 BFS큐에 넣지 말아야하므로 방문체크용 bool visited[101] 사용
  • 중복체크 안하면 메모리 초과 발생함 <- 사다리 올라갔다 내려갔다 무한반복함
• 현재 좌표 번호와, 몇번 굴렸는지 pair<int, int>로 관리함
• 이를 이용할 BFS 큐 사용

4. 소스코드

#include <iostream>
#include <queue>

using namespace std;

int N, M;
int teleport[101]; // i번째 좌표가 어디로 연결되는지
bool visited[101]; // 방문체크

void Input() {
	// freopen_s(new FILE*, "input.txt", "r", stdin);
	cin >> N >> M;
	for (int i = 1; i <= 100; i++) {
		teleport[i] = i;
	}
	for (int i = 0; i < N; i++) {
		int x, y;
		cin >> x >> y;
		teleport[x] = y;
	}
	for (int i = 0; i < M; i++) {
		int u, v;
		cin >> u >> v;
		teleport[u] = v;
	}

}

void BFS() {
	queue<pair<int, int> > qu; // 번호, 회수
	qu.push(make_pair(1, 0));
	visited[1] = true;

	while (!qu.empty()) {
		pair<int, int> now = qu.front();
		qu.pop();

		if (now.first == 100) {
			cout << now.second;
			return;
		}
		// 주사위 1~6 굴림
		for (int i = 1; i <= 6; i++) {
			int next = now.first + i; // 다음 이동 좌표 계산
			if (visited[next] == true) continue; // 이미 방문했다면 패스
			if (next > 100) continue; // 100 넘어가도 패스
			visited[next] = true;
			qu.push(make_pair(teleport[next], now.second + 1));
		}
	}
}

int main() {
	Input();

	BFS();

	return 0;
}