[백준 14562] 태권왕 (C++)

문제

---

태균이는 지금 태권도 겨루기 중이다. 지금은 상대에게 지고 있지만 지금부터 진심으로 경기하여 빠르게 역전을 노리려 한다.

태균이가 현재 할 수 있는 연속 발차기는 두가지가 있다.

1. A는 현재 점수만큼 점수를 얻을 수 있는 엄청난 연속 발차기이다. 하지만 상대 역시 3점을 득점하는 위험이 있다.
2. B는 1점을 얻는 연속 발차기이다.

현재 태균이의 점수 S와 상대의 점수 T가 주어질 때, S와 T가 같아지는 최소 연속 발차기 횟수를 구하는 프로그램을 만드시오.

 

입력

---

첫째 줄에 테스트 케이스의 수 C(1 ≤ C ≤ 100)이 주어진다. 둘째 줄부터 C줄에 걸쳐 테스트 케이스별로 현재 점수 S와 T가 공백을 사이에 두고 주어진다. (1 ≤ S < T ≤ 100)

 

출력

---

각 줄마다 S와 T가 같아지는 최소 연속 발차기 횟수를 출력한다.

 

 

문제 풀이

---

bfs 문제.

 

큐에 현재 태균이의 점수, 상대방의 점수, 현재까지 한 연속 발차기 횟수를 저장한 후, bfs 탐색을 진행하면 된다. 넓이 우선 탐색이므로 가장 먼저 얻어지는 먼저 태균이의 점수와 상대방의 점수가 같아지는 데이터에서 최소 연속 발차기 횟수를 얻어올 수 있다.

여러개의 테스트 케이스가 존재하므로 큐를 전역 변수로 선언했다면 큐를 비우는 작업이 필요하다.

 

아래는 코드.

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

struct score
{
	int s;
	int t;
	int count;
	score(int a, int b, int c)
	{
		s = a;
		t = b;
		count = c;
	}
};
queue<score> bfsQueue;

void popAll()
{
	while (!bfsQueue.empty())
	{
		bfsQueue.pop();
	}
}

void bfs(int s, int t)
{
	bfsQueue.push(score(s, t, 0));
	while (!bfsQueue.empty())
	{
		score current = bfsQueue.front();
		if (current.s == current.t)
		{
			cout << current.count << "\n";
			break;
		}
		if (current.s * 2 <= current.t + 3)
		{
			bfsQueue.push(score(current.s * 2, current.t + 3, current.count + 1));
		}
		bfsQueue.push(score(current.s + 1, current.t, current.count + 1));
		bfsQueue.pop();
	}
}

int main()
{
	cin.tie(NULL);
	ios::sync_with_stdio(false);

	int C, S, T;
	cin >> C;
	for (int i = 0; i < C; i++)
	{
		cin >> S >> T;
		bfs(S, T);
		popAll();
	}
	return 0;
}