14562번 : 태권왕

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

14562번: 태권왕

 

문제

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

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

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

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

 

입력

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

 

출력

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

 

---

소스코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        StringBuilder sb = new StringBuilder();

        int c = Integer.parseInt(br.readLine());
        for (int i = 0; i < c; i++) {
            st = new StringTokenizer(br.readLine());
            int s = Integer.parseInt(st.nextToken());
            int t = Integer.parseInt(st.nextToken());

            // bfs
            ArrayDeque<int[]> queue = new ArrayDeque<>();
            queue.add(new int[]{s, t});
            int result = 0;
            boolean flag = false;
            while(!queue.isEmpty()) {
                int size = queue.size();
                for (int j = 0; j < size; j++) {
                    int[] now = queue.poll();
                    int s1 = now[0] * 2;
                    int t1 = now[1] + 3;
                    int s2 = now[0] + 1;
                    int t2 = now[1];

                    if(s1 == t1 || s2 == t2) {
                        flag = true;
                        break;
                    }
                    if(s1 < t1) queue.add(new int[]{s1, t1});
                    if(s2 < t2) queue.add(new int[]{s2, t2});
                }
                result += 1;
                if(flag) break;
            }
            sb.append(result + "\n");
        }

        System.out.println(sb);
    }
}

 

해결방법

BFS 유형인 것만 판단하면 쉽게 풀 수 있다. 

연속 발차기를 할 수 있는 두 가지 경우를 모두 고려하는 BFS 연산을 하면 된다.