[자바] 백준 14562 - 태권왕 (java)

 문제 : boj14562

---

 

필요 알고리즘 개념

• 너비 우선 탐색 (bfs)
  
  • 너비 우선 탐색을 떠오르기 힘들 수 있고 다른 풀이도 존재하는 문제이다. 이하 풀이는 너비 우선 탐색으로 진행한다.
• 백트래킹
  • 부가적으로 백트래킹 개념도 넣으면 좋다.

※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다.

 

---

 

풀이

  일반적으로 bfs는 목적지(이 문제에서는 t에 해당)는 고정되어 있고 목적지까지 탐색해나가곤 한다. 하지만 출발지점과 목적지를 동시에 사용해서 bfs를 한다고 생각하면 이 문제를 bfs로 생각해볼 수 있다. 우선 bfs를 모른다면 이 글을 참고하자. 풀이에서 추가적으로 사용하는 백트래킹을 모른다면 이 글을 참고하자.

 

  (s, t, ith)를 하나의 데이터(ith는 몇번째인지를 나타낸다)로 생각해보자. 시작점은 정해져 있으나, 목적지는 s와 t가 동일해질 때 까지이다. 이 때 bfs로 진행 가능한 간선은 2가지이다.

1. (s, t, ith) -> (2s, t+3, ith+1)

2. (s, t, ith) -> (s+1, t, ith+1)

 

이 때 진행하면서 변경된 s와 t가 동일한 값이 되었다면, 해당 ith를 출력해주면 된다. 위에서 말한 bfs를 작성해보면 다음과 같다.

Queue<int[]> q = new ArrayDeque<>();
q.add(new int[]{s,t,0});

while (!q.isEmpty()) {
    int[] cur = q.poll();
    int curS = cur[0];	// 현재 뽑은 지점의 s
    int curT = cur[1];	// 현재 뽑은 지점의 t
    int ith = cur[2];	// 현재 뽑은 지점이 몇번째였는지
    if (curS == curT) {	// s와 t가 동일하다면 ith가 답이다.(bfs이므로 찾아진 순간이 '최소' 횟수에 해당함)
        return ith;
    }

    q.add(new int[]{curS*2, curT+3, ith+1});	// 간선1
    q.add(new int[]{curS+1, curT, ith+1});		// 간선2
}

 

 

  그런데, 위처럼하면 사실 낭비되는 경우가 많다. 문제에서 요구하는 '최소' 횟수를 찾기 위해 bfs를 쓰고는 있지만, 완전 탐색에 가까운 방식으로 진행중이므로 매번 x2번씩 진행된다. 예를들어 s=34, t=59 라고 한다면, 대충 생각해봐도 1점을 얻는 발차기만 해도 25번만에 가능하다. 이 때, 매번 2배씩 늘어나며 25번을 진행하게 되니 2^25번 정도 돌아가게 될 것이라 매우 비효율적이다.

 

  그렇다면 어느 경우에 더이상 판단하지 않아도 될까? 결론적으로 s>t인 경우이다. 이 문제에서 s가 t를 넘는 순간, s에서 t가 될 방법은 없다. s가 3이 넘을 때 부터, (2s, t+3)에서 더 작은 t로 갈 가능성이 전혀 없다. s가 1, 2일 때는 어떤 경우를 해봐도 t가 더 작아질 수 없다. 그리고 (s+1, t)는 당연히  더 작은 t로 갈 수 없다. 아무튼 그러니 s>t인 경우는 진행을 멈추자(백트래킹). 즉, 위 코드부분에서 아래와 같이 추가한다.

Queue<int[]> q = new ArrayDeque<>();
q.add(new int[]{s,t,0});

while (!q.isEmpty()) {
    int[] cur = q.poll();
    int curS = cur[0];	// 현재 뽑은 지점의 s
    int curT = cur[1];	// 현재 뽑은 지점의 t
    int ith = cur[2];	// 현재 뽑은 지점이 몇번째였는지
    if (curS == curT) {	// s와 t가 동일하다면 ith가 답이다.(bfs이므로 찾아진 순간이 '최소' 횟수에 해당함)
        return ith;
    }
	if (curS > curT)	// s>t라면 거기서 멈춘다.
		continue;
    q.add(new int[]{curS*2, curT+3, ith+1});	// 간선1
    q.add(new int[]{curS+1, curT, ith+1});		// 간선2
}

 

 

---

 

코드 : github

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

public class Main {
    private int getAnswer(int s, int t) {
        Queue<int[]> q = new ArrayDeque<>();
        q.add(new int[]{s,t,0});
        while (!q.isEmpty()) {
            int[] cur = q.poll();
            int curS = cur[0];
            int curT = cur[1];
            int ith = cur[2];
            if (curS == curT) {
                return ith;
            }
            if (curS > curT)
                continue;
            q.add(new int[]{curS*2, curT+3, ith+1});
            q.add(new int[]{curS+1, curT, ith+1});
        }
        return -1;
    }

    private void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int c = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();
        while (c-->0) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int s = Integer.parseInt(st.nextToken());
            int t = Integer.parseInt(st.nextToken());
            sb.append(getAnswer(s, t)).append('\n');
        }
        System.out.print(sb);
    }

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }
}