[알고리즘] 백준 14562번: 태권왕 (C++), 범위 오류

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

14562번: 태권왕

이번 문제를 풀면서 저번에 포스팅했던 리모컨 문제가 떠올랐었다.

(https://draw-code-boy.tistory.com/99)

 

솔루션

간단한 BFS 문제였다. S와 T의 점수가 주어지면 두 가지 방법으로 S의 점수를 올려준다.

1. S의 점수가 2배가 된다. 단, T의 점수에는 3점이 추가된다.
2. S의 점수에 1점이 추가된다.

두 가지 경로를 가지고 BFS를 짜주면 된다.

단, 이번 문제에서 주의해야 할 사항이 2가지 존재한다.

---

1) 한 번 나온 스코어는 건드리지 않는다.

예를 들어, 2 : 4 가 나오고 있다 치면 다른 경로를 통해서도 2 : 4 가 나오는 경우가 있다.

둘 중에 더 빠른 경로가 나온 이상 다신 2 : 4라는 점수를 건드리지 않도록 한다.

>> 최솟값을 구하는 과정

 

아래는 BFS에서 경로 탐색의 조건을 가져온 부분이다.

if문에서

score[y * 2][x + 3] == 0

score[y + 1][x] == 0

두 조건들이 다신 건드리지 않게 해주는 조건에 해당된다.

if (y * 2 < MAX && x + 3 < MAX && score[y * 2][x + 3] == 0) {
	q.push(make_pair(y * 2, x + 3));
	score[y * 2][x + 3] = score[y][x] + 1;
}
if (y + 1 < MAX && x < MAX && score[y + 1][x] == 0) {
	q.push(make_pair(y + 1, x));
	score[y + 1][x] = score[y][x] + 1;
}

 

2) 범위를 잘 생각해봐야 한다.

문제에서는 S와 T가 100 이하의 수로 주어진다고 되어있다. 그렇다고 해서 점수 또한 100까지만 올릴 수 있는 건 아니라고 생각해야 한다. (이번 포스팅의 이유)

만약 저 생각을 못 하고서 코드를 짠다면 다음 반례가 존재한다.

[input]
1
1 100
[output]
99
[answer]
10

100까지만 잡았을 때는 100에서 점수가 안 올라가므로 1에서부터 1점씩 밖에 못 올려서 99번이 된다.

하지만, 조금 넉넉하게 200까지 잡아주면 10이라는 답을 도출할 수 있다.

>> 점수가 100을 넘길 수도 있다는 생각을 할 수 있어야 한다.

---

[범위 설정 오류 코드]

#include <iostream>
#include <queue>
#include <utility>
using namespace std;

int T;
int score[101][101] = { 0, };

void reset() {
	for (int i = 1; i <= 100; i++) {
		for (int j = 1; j <= 100; j++) {
			score[i][j] = 0;
		}
	}
}

int bfs(int s1, int s2) {
	queue<pair<int, int>> q;
	q.push(make_pair(s1, s2));
	while (!q.empty()) {
		int y = q.front().first;
		int x = q.front().second;

		if (y == x) {
			return score[y][x];
		}
		q.pop();

		if (y * 2 <= 100 && x + 3 <= 100 && score[y * 2][x + 3] == 0) {
			q.push(make_pair(y * 2, x + 3));
			score[y * 2][x + 3] = score[y][x] + 1;
		}
		if (y + 1 <= 100 && x <= 100 && score[y + 1][x] == 0) {
			q.push(make_pair(y + 1, x));
			score[y + 1][x] = score[y][x] + 1;
		}
	}
}

int main() {
	cin >> T;
	for (int t = 1; t <= T; t++) {
		int s1, s2;
		cin >> s1 >> s2;
		cout << bfs(s1, s2) << '\n';
		reset();
	}
	return 0;
}

[AC 코드]

#include <iostream>
#include <queue>
#include <utility>
using namespace std;
#define MAX 200 + 1

int T;
int score[MAX][MAX] = { 0, };

void reset() {
	for (int i = 0; i < MAX; i++) {
		for (int j = 0; j < MAX; j++) {
			score[i][j] = 0;
		}
	}
}

int bfs(int s1, int s2) {
	queue<pair<int, int>> q;
	q.push(make_pair(s1, s2));
	while (!q.empty()) {
		int y = q.front().first;
		int x = q.front().second;

		if (y == x) {
			return score[y][x];
		}
		q.pop();

		if (y * 2 < MAX && x + 3 < MAX && score[y * 2][x + 3] == 0) {
			q.push(make_pair(y * 2, x + 3));
			score[y * 2][x + 3] = score[y][x] + 1;
		}
		if (y + 1 < MAX && x < MAX && score[y + 1][x] == 0) {
			q.push(make_pair(y + 1, x));
			score[y + 1][x] = score[y][x] + 1;
		}
	}
}

int main() {
	cin >> T;
	for (int t = 1; t <= T; t++) {
		int s1, s2;
		cin >> s1 >> s2;
		cout << bfs(s1, s2) << '\n';
		reset();
	}
	return 0;
}