문제

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

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

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

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

입력

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

출력

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

import java.util.*;
import java.io.*;
public class Main {
    static int S, T;
    public static void main (String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        st = new StringTokenizer(br.readLine());
        int t = Integer.parseInt(st.nextToken());
        for (int k = 0; k < t; k++) {
            st = new StringTokenizer(br.readLine());
            S = Integer.parseInt(st.nextToken());
            T = Integer.parseInt(st.nextToken());

            System.out.println(BFS());

        }
    }
    public static int BFS() {
        Queue<Node> q = new LinkedList<>();
        q.add(new Node(S, T, 0));

        while(!q.isEmpty()) {
            Node n = q.poll();
            int cnt = n.cnt;
            if (n.kS == n.kT) {
                return cnt;
            }
            if (n.kS > n.kT)
                continue;
            q.add(new Node(n.kS+1, n.kT, cnt+1));
            q.add(new Node(n.kS*2, n.kT+3, cnt+1));
        }
        return -1;
    }
}
class Node {
    int kS, kT, cnt;
    Node (int kS, int kT, int cnt) {
        this.kS = kS;
        this.kT = kT;
        this.cnt = cnt;
    }
}

• BFS문제를 풀다보면 방문처리하는게 버릇되서 쓸데없는 로직구성을 한다.
• 해당 문제는 수가 줄어들 일이 없기 때문에 태균이 점수가 상대방 점수보다 높을 경우의 연산은 필요하지 않다.