[Java] 백준 14562 태권왕 - 실버2

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

14562번: 태권왕

 

 

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

public class Main {
  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    int testCaseCnt = Integer.parseInt(br.readLine());

    for (int tc=0; tc<testCaseCnt; tc++) {
      StringTokenizer st = new StringTokenizer(br.readLine());
      int scoreA = Integer.parseInt(st.nextToken()); //항상 scoreA < scoreB
      int scoreB = Integer.parseInt(st.nextToken());

      Queue<List<Integer>> queue = new LinkedList<>();
      List<Integer> tmp = new ArrayList<>();
      tmp.add(scoreA); //점수
      tmp.add(scoreB); //목표점수
      tmp.add(0); //발차기 횟수
      queue.add(tmp);

      int result = 0;
      while (!queue.isEmpty()) {
        List<Integer> list = queue.poll();
        int score = list.get(0);
        int scoreGoal = list.get(1);
        int kickCnt = list.get(2);

        if (score*2 == scoreGoal+3 || score+1 == scoreGoal) {
          result = kickCnt +1;
          break;
        }

        if (score*2 < scoreGoal+3) {
          tmp = new ArrayList<>();
          tmp.add(score*2); //점수
          tmp.add(scoreGoal+3); //목표점수
          tmp.add(kickCnt+1); //발차기 횟수
          queue.add(tmp);
        }

        if (score+1 < scoreGoal) {
          tmp = new ArrayList<>();
          tmp.add(score+1); //점수
          tmp.add(scoreGoal); //목표점수
          tmp.add(kickCnt+1); //발차기 횟수
          queue.add(tmp);
        }
      }

      System.out.println(result);
    }
  }
}

• queue에는 [현재 scoreA, 현재 scoreB, 현재 발차기 횟수] 3가지 데이터를 저장한다
• 큐에 초기 값 [scoreA, scoreB, 0] 을 넣은 후
• 큐가 빌 때까지 반복한다
  • 만약 scoreA*2 가 scoreGoal+3 과 같거나/ scoreA + 1이 scoreGoal과 같으면 kickCnt+1 이 정답이다
  • scoreA * 2 가 scoreGoal+3보다 작으면 아직 도착하지 않은 거니 큐에 넣어준다
  • scoreA +1 이 scoreGoal보다 작으면 마찬가지로 아직 도착하지 않은 거니 큐에 넣어준다

 

 

 

최소 발차기 수니까 최소값부터 큐에 들어가고 나오는 bfs가 맞는 방법인 것 같다.