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

문제링크 : https://www.acmicpc.net/problem/14562

14562번: 태권왕

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 987654321;

struct Info
{
    int s, t, cnt;
};

void bfs(int S, int T, int CNT)
{
    queue<Info>q;
    q.push({S,T,CNT});
    while(!q.empty())
    {
        Info cur = q.front(); q.pop();

        if(cur.s > cur.t) continue; 

        else if(cur.s == cur.t) 
        {
            cout << cur.cnt <<"\n"; 
            break;
        }

        q.push({cur.s * 2, cur.t + 3, cur.cnt+1}); //발차기 1번
        q.push({cur.s + 1, cur.t, cur.cnt+1}); //발차기 2번
    }
}

int main()
{
    ios_base::sync_with_stdio(0); 
	cin.tie(0);

    int C;
    cin >> C;
    while(C--)
    {
        int S, T;
        cin >> S >> T;
        bfs(S,T,0);
    }

    return 0;
}

BFS 문제이다.

발차기의 경우가 S가 2배, T가 + 3 또느 S만 +1 이렇게 2가지가 있다.

큐에 S의 점수, T의 점수, 카운트를 넘겨준다.

S가 T보다 커지는 순간부터는 무조건 같지 않게 되므로 continue;로 넘기고, 같아 질때 출력한다.

 

발차기가 2가지 이므로 큐에 현재 S*2, T+3, 카운트 / S+1, T, 카운트 이렇게 2가지를 같이 넣어주며, S와 T가 맞는 순간에 출력하고 break 해준다.