백준 16928 뱀과 사다리 게임 (c++) : 피너클

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

16928번: 뱀과 사다리 게임

bfs문제다.

cin >> n >> m;
for (int i = 0; i < n; i++) {
	int a, b;
	cin >> a >> b;
	map[a] = b;
}
for (int i = 0; i < m; i++) {
	int a, b;
	cin >> a >> b;
	map[a] = -b;
}

값들을 입력받는다. 여기서 사다리는 +로, 뱀은 -로 저장한다.

int bfs() {
	queue<pair<int, int>> q;
	q.push({ 1, 0 });
	visited[1] = true;

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

bfs함수의 기본 세팅을 해준다. 처음 자리가 1이니 q에 넣어주고 visiteid[1]도 true로 바꾼다.

int now는 현재 있는 위치고 int time은 현재 자리까지 오는데 걸린 시간이다.

		if (now == 100) return time;

만약 현재 위치가 100이라면 그대로 time을 리턴한다.

		for (int i = 1; i <= 6; i++) {
			int next = now + i;
			if (!visited[next] && next <= 100) {
				if (map[next] == 0) {
					q.push({ next, time + 1 });
					visited[next] = true;
				}
				else if (map[next] > 0) {
					q.push({ map[next], time + 1 });
					visited[map[next]] = true;
				}
				else {
					q.push({ -map[next], time + 1 });
					visited[-map[next]] = true;
				}
			}
		}

주사위는 1부터 6까지 있으니 반복문을 6까지 돌려준다.

int next는 now에서 1~6의 숫자를 더한것이다.

만약 next가 아직 방문하지 않은 곳이고 100보다 작다면 q안에 값을 집어넣을것이다.

만약 map[next]가 0이라면 사다리도 뱀도 없다는 뜻이니 그대로 q에 집어넣는다.

만약 map[next]가 0보다 크다면 사다리가 있다는 뜻이니 q에 사다리를 타고 간 곳의 위치를 넣는다.

만약 map[next]가 0보다 작다면 뱀이 있다는 뜻이니 q에 뱀을 타고 내려간 곳의 위치를 넣는다.

#include <iostream>
#include <string.h>
#include <queue>

using namespace std;

int n, m;
int map[101];
bool visited[101];

int bfs() {
	queue<pair<int, int>> q;
	q.push({ 1, 0 });
	visited[1] = true;

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

		if (now == 100) return time;

		for (int i = 1; i <= 6; i++) {
			int next = now + i;
			if (!visited[next] && next <= 100) {
				if (map[next] == 0) {
					q.push({ next, time + 1 });
					visited[next] = true;
				}
				else if (map[next] > 0) {
					q.push({ map[next], time + 1 });
					visited[map[next]] = true;
				}
				else {
					q.push({ -map[next], time + 1 });
					visited[-map[next]] = true;
				}
			}
		}
	}
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	memset(map, 0, sizeof(map));
	memset(visited, false, sizeof(visited));

	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		int a, b;
		cin >> a >> b;
		map[a] = b;
	}
	for (int i = 0; i < m; i++) {
		int a, b;
		cin >> a >> b;
		map[a] = -b;
	}
	cout << bfs() << endl;
}