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

📌문제 링크

---

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

📌문제 설명

---

최대 S와 T값이 100밖에 안된다. 엄청난 연속 발차기는 최대 8번까지만 가능하므로 2중 for문으로도 충분히 돌아간다. 기본 bfs로 s와 t값과 발차기 횟수를 queue에 넣고 s와 t값이 같을때 횟수를 출력하고 종료한다.

📌코드

---

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <climits>
using namespace std;
int C;
struct comp{
    int a, b, cnt;
};
queue<comp> q;

void bfs(int s, int t){
    q.push({s, t, 0});
    while (!q.empty()){
        auto [s, t, cnt] = q.front(); q.pop();
        if(s == t){
            cout << cnt << '\n';
            return;
        }
        if(s * 2 <= t + 3){
            q.push({s * 2, t + 3, cnt + 1});
        }
        if(s + 1 <= t){
            q.push({s + 1, t, cnt + 1});
        }
    }
    
}

void init(){
    while(!q.empty())q.pop();
}

void solve(int s, int t){
    init();
    bfs(s, t);
}

void input(){
    cin >> C;
    while(C--){
        int S, T;
        cin >> S >> T;
        solve(S, T);
    }
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    input();
    return 0;
}