[백준/CPP/C++] 14562번 - 태권왕

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

14562번: 태권왕

 

 

BFS문제이다.

다른 최단거리 문제와는 다르게, 2번 발차기를 사용할 경우 목적지의 값도 증가한다는 때문에 조금 헤맸다..

 

#include <bits/stdc++.h>
using namespace std;

int main(void) {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int tc; cin >> tc;

	while (tc) {

		int a, b; cin >> a >> b;

		queue <tuple <int, int, int>> tk;
		tuple <int, int, int> tmp;

		tk.push({ a, 0, b });

		while (!tk.empty()) {
			tmp = tk.front(); tk.pop();

			// 현재 위치 now, 목적지 des, 이동 횟수 cost
			int now = get<0>(tmp);
			int des = get<2>(tmp);
			int cost = get<1>(tmp);

			// 목적지에 도착했다면, COST 출력하고 break
			if (now == des) {
				cout << cost << '\n';
				break;
			}

			// 2번 발차기. + 1점 획득
			int nX = now + 1;

			// 1점씩 획득하는 2번 발차기는 상대의 점수에 영향을 미치지 않는다.
			if (nX <= des) {
				tk.push({ nX, cost + 1, des });
			}

			// 1번 발차기, 현재 점수의 2배 획득
			int double_X = now * 2;

			// 1번 발차기는 상대의 점수에 영향을 준다.
			// 그러므로 상대의 점수 + 3점만 넘어가지 않으면 queue에 push해준다.
			if (double_X <= des + 3) {
				// 상대 점수의 값도 올려주어야함!
				tk.push({ double_X, cost + 1, des + 3 });
			}

		}
		tc--;
	}


}

 

마지막 if문인 des + 3을 지정해주는 부분에서 조금 생각을 많이 했다....ㅠ