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

프로그래밍/PS

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

유태정 2021. 5. 2. 22:14

16928번: 뱀과 사다리 게임

첫째 줄에 게임판에 있는 사다리의 수 N(1 ≤ N ≤ 15)과 뱀의 수 M(1 ≤ M ≤ 15)이 주어진다. 둘째 줄부터 N개의 줄에는 사다리의 정보를 의미하는 x, y (x < y)가 주어진다. x번 칸에 도착하면, y번 칸으

www.acmicpc.net

풀이과정

오답: 틀렸습니다. (22%)

1. 크기가 100인 int 배열 step을 정의한다. 여기에는 각 위치에 도달하기까지 최소 횟수가 저장된다.

2. 재귀함수를 이용하여 모든 경우를 탐색한다.

2-1. 위치 1부터 시작하여, 6칸 이내에 있는 사다리와 뱀을 타고 각각 이동하고 그 위치에서 6칸을 이동한다.

2-2. 만약 새로 이동할 위치에 해당하는 step 배열 값이 현재의 step에 1을 더한 값보다 작다면 이동하지 않는다. 지금보다 최소 경로로 이미 이동했다는 뜻이기 때문이다.

3. 모든 경우를 탐색했다면 step[99]의 값이 정답이다.

어떤 질문글의 답변에서 힌트를 얻었다. 사다리나 뱀을 만나면 무조건 타고 움직여야 한다. 그러므로 내 경우에 사다리와 뱀의 시작점에 해당하는 step 값을 -1로 하여, 주사위로 이동하여 그 위치에 이동하게 되는 경우를 배제시키면 될 것 같다.

글 읽기 - 반례가 뭐가 있는지 잘 모르겠습니당 ㅠㅠ

댓글을 작성하려면 로그인해야 합니다.

www.acmicpc.net

#include <bits/stdc++.h>

using namespace std;

#define TC(T) int T; cin >> T; while(T--)
#define FAST_IO cin.tie(NULL); ios::sync_with_stdio(false);
#define FOR(i, N) for(int i = 0; i < N; ++i)
#define INF 987654321
#define ERR 1e-13
#define EL "\n"

vector<pair<int, int>> L, S;
vector<int> step;

void travel(int pos){
	// Find ladders and snakes within 6 spaces
	for (auto& W : { L, S })
		for (auto& el : W) {
			auto& [from, to] = el;
			if (from >= pos && from <= pos + 6 && step[pos - 1] + 1 < step[to - 1]) {
				step[to - 1] = step[pos - 1] + 1;
				travel(to);
			}
		}
	// move 6 spaces
	int jump = pos + 6 > 100 ? 100 - pos : 6;
	if (step[pos - 1] + 1 < step[pos + jump - 1]) {
		step[pos + jump - 1] = step[pos - 1] + 1;
		travel(pos + jump);
	}
}

int main(){
#ifdef DEBUG
	freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
#endif
	FAST_IO;

	int N, M;
	cin >> N >> M;

	L = vector<pair<int, int>>(N);
	FOR(i, N)
		cin >> L[i].first >> L[i].second;
	S = vector<pair<int, int>>(M);
	FOR(i, M)
		cin >> S[i].first >> S[i].second;

	step = vector<int>(100, numeric_limits<int>::max());
	step[0] = 0;
	travel(1);

	cout << step[99] << EL;

	return 0;
}

오답: 틀렸습니다. (7%)

위 코드에서 사다리와 뱀의 시작점에 해당하는 step의 값을 -1로 하여 해당 칸에 정지할 수 없도록 했지만 오답이 나왔다. 모르겠다.

#include <bits/stdc++.h>

using namespace std;

#define TC(T) int T; cin >> T; while(T--)
#define FAST_IO cin.tie(NULL); ios::sync_with_stdio(false);
#define FOR(i, N) for(int i = 0; i < N; ++i)
#define INF 987654321
#define ERR 1e-13
#define EL "\n"

vector<pair<int, int>> L, S;
vector<int> step;

void travel(int pos) {
	// Find ladders and snakes within 6 spaces
	for (auto& W : { L, S })
		for (auto& el : W) {
			auto& [from, to] = el;
			if (from >= pos && from <= pos + 6 && step[pos - 1] + 1 < step[to - 1]) {
				step[to - 1] = step[pos - 1] + 1;
				travel(to);
			}
		}
	// move 6 spaces
	int jump = pos + 6 > 100 ? 100 - pos : 6;
	if (step[pos - 1] + 1 < step[pos + jump - 1]) {
		step[pos + jump - 1] = step[pos - 1] + 1;
		travel(pos + jump);
	}
}

int main() {
#ifdef DEBUG
	freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
#endif
	FAST_IO;

	int N, M;
	cin >> N >> M;

	L = vector<pair<int, int>>(N);
	FOR(i, N)
		cin >> L[i].first >> L[i].second;
	S = vector<pair<int, int>>(M);
	FOR(i, M)
		cin >> S[i].first >> S[i].second;

	step = vector<int>(100, numeric_limits<int>::max());
	FOR(i, N)
		step[L[i].first - 1] = -1;
	FOR(i, M)
		step[S[i].first - 1] = -1;
	step[0] = 0;
	travel(1);

	cout << step[99] << EL;

	return 0;
}

오답: 틀렸습니다.(0%)

알고리즘 분류가 너비 우선 탐색으로 돼 있어서 그렇게 바꿔봤다.

그런데 제출하자 마자 틀렸다.

#define DEBUG

#include <bits/stdc++.h>

using namespace std;

#define TC(T) int T; cin >> T; while(T--)
#define FAST_IO cin.tie(NULL); ios::sync_with_stdio(false);
#define FOR(i, N) for(int i = 0; i < N; ++i)
#define INF 987654321
#define ERR 1e-13
#define EL "\n"

int main() {
#ifdef DEBUG
	freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
#endif
	FAST_IO;

	int N, M;
	cin >> N >> M;
	vector<pair<int, int>> ladders(N);
	FOR(i, N)
		cin >> ladders[i].first >> ladders[i].second;
	vector<pair<int, int>> snakes(M);
	FOR(i, M)
		cin >> snakes[i].first >> snakes[i].second;

	queue<pair<int, int>> BFS;
	vector<bool> visited(100, false);
	visited[0] = true;
	BFS.push(make_pair(1, 0));
	int min_step = -1;
	while (!BFS.empty()) {
		auto [pos, step] = BFS.front();
		BFS.pop();
		if (pos == 100) {
			min_step = step;
			break;
		}
		for(auto& vehicle : {ladders, snakes})
			for (auto& jump : vehicle) {
				auto& [from, to] = jump;
				if (from > pos && from - pos < 6 && !visited[to - 1]) {
					visited[to - 1] = true;
					BFS.push(make_pair(to, step + 1));
				}
			}
		if (pos + 6 < 100 && !visited[pos + 5]) {
			visited[pos + 5] = true;
			BFS.push(make_pair(pos + 6, step + 1));
		}
		else if (pos + 6 > 100) {
			visited[99] = true;
			BFS.push(make_pair(100, step + 1));
		}
	}

	cout << min_step << EL;

	return 0;
}

오답: 틀렸습니다.(7%)

직관적으로 코드를 다시 작성했다.

아마도 주사위를 굴리는 부분이 잘못 된 것 같다.

반례가 뭐가 있을지 생각해봐야 한다.

위에 링크한 질문글에서 킹갓제너럴 dotorya 선생님의 답변에 의하면 가중치가 0인 간선이 있는 BFS에서 queue를 사용하면 잘못된 값이 나올 수 있다고 한다.

BFS를 queue를 안 쓰고 할 수 있던가?

한 번 가능한 간선을 모두 생성하여 BFS를 구현해보자.

#include <bits/stdc++.h>

using namespace std;

#define TC(T) int T; cin >> T; while(T--)
#define FAST_IO cin.tie(NULL); ios::sync_with_stdio(false);
#define FOR(i, N) for(int i = 0; i < N; ++i)
#define INF 987654321
#define ERR 1e-13
#define EL "\n"

int main() {
#ifdef DEBUG
	freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
#endif
	FAST_IO;

	int N, M;
	cin >> N >> M;
	vector<pair<int, int>> ladders(N), snakes(M);
	FOR(i, N) cin >> ladders[i].first >> ladders[i].second;
	FOR(i, M) cin >> snakes[i].first >> snakes[i].second;

	queue<pair<int, int>> BFS;
	vector<bool> visited(100, false);
	BFS.push(make_pair(1, 0));
	visited[0] = true;
	int count = 0;
	while (!BFS.empty()) {
		auto [pos, step] = BFS.front();
		BFS.pop();
		if (pos == 100) {
			count = step;
			break;
		}
		for (auto& ladder : ladders)
			if (ladder.first == pos && !visited[ladder.second - 1]) {
				visited[ladder.second - 1] = true;
				BFS.push(make_pair(ladder.second, step));
			}
		for (auto& snake : snakes)
			if (snake.first == pos && !visited[snake.second - 1]) {
				visited[snake.second - 1] = true;
				BFS.push(make_pair(snake.second, step));
			}
		for (int i = 1; i <= 6; i++)
			if (pos + i <= 100 && !visited[pos + i - 1]) {
				visited[pos + i - 1] = true;
				BFS.push(make_pair(pos + i, step + 1));
			}
	}

	cout << count << EL;

	return 0;
}

정답: 맞았습니다!!!

가능한 간선을 새로 만들고 그것을 이용해 BFS를 진행했다.

깔끔하게 정답이 나왔다. 가중치가 0인 간선 때문이 맞은 것 같다.

이에 대해서 생각할 필요가 있다...

#include <bits/stdc++.h>

using namespace std;

#define TC(T) int T; cin >> T; while(T--)
#define FAST_IO cin.tie(NULL); ios::sync_with_stdio(false);
#define FOR(i, N) for(int i = 0; i < N; ++i)
#define INF 987654321
#define ERR 1e-13
#define EL "\n"

int main() {
#ifdef DEBUG
	freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
#endif
	FAST_IO;

	int N, M;
	cin >> N >> M;
	vector<pair<int, int>> ladders(N), snakes(M);
	FOR(i, N) cin >> ladders[i].first >> ladders[i].second;
	FOR(i, M) cin >> snakes[i].first >> snakes[i].second;

	vector<pair<int, int>> relations;
	for (int i = 1; i < 100; i++) {
		for (int j = 0; j <= 6; j++) {
			bool skipped = false;
			for (auto& ladder : ladders)
				if (ladder.first == i + j) {
					relations.push_back(make_pair(i, ladder.second));
					skipped = true;
				}
			for (auto& snake : snakes)
				if (snake.first == i + j) {
					relations.push_back(make_pair(i, snake.second));
					skipped = true;
				}
			if (!skipped && i + j <= 100)
				relations.push_back(make_pair(i, i + j));
		}
	}

	queue<pair<int, int>> BFS;
	BFS.push(make_pair(1, 0));
	vector<bool> visited(100, false);
	visited[0] = true;
	while (!BFS.empty()) {
		auto [pos, step] = BFS.front();
		BFS.pop();
		if (pos == 100) {
			cout << step << EL;
			break;
		}

		for(auto& relation : relations)
			if (relation.first == pos && !visited[relation.second - 1]) {
				visited[relation.second - 1] = true;
				BFS.push(make_pair(relation.second, step + 1));
			}
	}

	return 0;
}