c++ 14562번 태권왕 (백준)

#include <bits/stdc++.h>

using namespace std;

int main(void)
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	int t;
	cin >> t;
	
	while(t--) {
		int a, b;
		queue<tuple<int, int, int> > q;
		cin >> a >> b;
		q.push(make_tuple(a, b, 0));
		
		while(!q.empty()) {
			int x = get<0>(q.front());
			int y = get<1>(q.front());
			int v = get<2>(q.front());
			q.pop();
			x *= 2;
			y += 3;
			v++; 
			if(x < y) q.push(make_tuple(x, y, v));
			else if(x==y) {
				cout << v << '\n';
				break;
			} 
			
			x /= 2;
			y -= 3;
			x++;
			if(x < y) q.push(make_tuple(x, y, v));
			else if(x==y) {
				cout << v << '\n';
				break;
			}
		}
	}
}

풀이 : BFS

 

두가지 경우가 있습니다. 나의 점수의 2배를 하되, 상대의 점수에 +3. 다른 것은 자신의 점수에 +1을 하는 것입니다.

 

이 두가지의 경우로 BFS을 돌려서 몇 번 시행해야 나와 상대의 점수가 같아지는 지를 알 수 있습니다.

단 나의 점수가 상대의 점수를 넘어가게 되면, 이 경로로는 더이상 BFS을 돌릴 필요가 없어집니다.

 

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

14562번: 태권왕