백준 16928번: 뱀과 사다리 게임 (C++)

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

16928번: 뱀과 사다리 게임

 

 

풀이

완전탐색인거 같은데 재방문할 필요가 없고 최소 거리를 구해야 하기 때문에 BFS를 이용했다.

 

뱀과 사다리에 접근했을 때 pair를 이용하면 전체 탐색을 해야할 것 같아서

map을 이용해 뱀 혹은 사다리에 키 값이 존재하면 바로 이동지점으로 갈 수 있게 했다.

 

다음 위치가 100 이상이면 탐색하지 않고 100일 때 방문 횟수를 체크하고 BFS를 종료시켰다.

 

 

 

전체 코드

#include <iostream>
#include <string.h>
#include <algorithm>
#include <cmath>
#include <vector>
#include <queue>
#include <unordered_map>

using namespace std;

int N, M;
int board[101] = { 0, };
int visited[101] = { 0, };

unordered_map<int, int> ladder;
unordered_map<int, int> snake;

int bfs(int y) {
	queue<int> q;
	q.push(y);
	visited[y] = 1;

	while (!q.empty()) {
		int now = q.front();
		q.pop();

		for (int i = 1; i <= 6; i++) {
			int next = now + i;

			if (next > 100) continue;
			if (next == 100) return visited[next] = visited[now] + 1;

			if (visited[next] != 0) continue;

			if (board[next] == 2) { // 사다리
				visited[next] = visited[now] + 1;
				if (visited[ladder[next]] != 0) continue;
				visited[ladder[next]] = visited[next];
				q.push(ladder[next]);
				continue;
			}
			if (board[next] == 3){ // 뱀
				visited[next] = visited[now] + 1;
				if (visited[snake[next]] != 0) continue;
				visited[snake[next]] = visited[next];
				q.push(snake[next]);
				continue;
			}

			visited[next] = visited[now] + 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++) {
		pair<int, int> p;
		cin >> p.first >> p.second;
		board[p.first] = 2; // 사다리
		ladder.insert(p);
	}
	for (int i = 0; i < M; i++) {
		pair<int, int> p;
		cin >> p.first >> p.second;
		board[p.first] = 3; // 뱀
		snake.insert(p);
	}

	cout << bfs(1) - 1;
	
}