[백준] 14562번: 태권왕 (python)

14562번: 태권왕

---

문제 )

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

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

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

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

 

 

입력 :

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

 

 

출력 :

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

 

 

 

 

풀이)

 

할 수 있는 모든 방법을 체크해보고 그 중에서 가장 최소 횟수를 구해야 하므로 처음 보자마자재귀를 이용한 백트래킹이 생각이 났다.그렇게 나온 코드는 다음과 같다.

 

def recur(s, t, cnt):
    global answer
    # 불필요한 재귀를 차단
    if s < t + 1:
        # 정답 요건에 도달했을 때, 최소값으로 정답갱신
        if s == t:
            answer = min(answer, cnt)
            return
        
        # 엄청난 연속 발차기
        recur(s + s, t + 3, cnt + 1)
        # 1점을 얻는 연속 발차기
        recur(s + 1, t, cnt + 1)
 
 
c = int(input())
for _ in range(c):
    # s와 t가 같아지는 최소 횟수를 구해야 하므로.
    # 백트래킹이 먼저 생각남.
    answer = 99999
    s, t = map(int, input().split())
    recur(s, t, 0)
    print(answer)

 

내 코드를 보니 어떻게 보아도 백트래킹이지 이 문제의 분류인 너비 우선 탐색은 잘 모르겠어서 

다른 분들의 코드를 살펴 보았다.

 

다른 분의 코드를 보며 깨달은 점.- BFS는 최단 경로를 찾는데 최적화 되어 있는 알고리즘이다.- 백트래킹도 좋지만 값이 커질 경우 현저히 속도가 느려질 가능성이 있으므로 가지치기(프루닝)이 중요해진다.- BFS의 경우에는 "대체로" 방문 유무인 visited 를 사용하지 않는다.

 

 

 

BFS 풀이는 다음과 같다.

 

# BFS로 풀이를 진행할 예정이므로 deque 사용
from collections import deque
 
def BFS():
    queue.append([s, t, 0])
    answer = 9999999
 
    while queue:
        a, b, c = queue.popleft()
        # 무한루프에 빠지는 것을 막기 위해
        # 밑의 조건이 없다면 a가 b를 넘어섰을때 멈추지 못하고
        # 계속 계산이 진행되므로 메모리 초과가 나게 된다.
        if a < b + 1:
            if a == b:
                answer = min(answer, c)
                return answer
 
            queue.append([a + a, b + 3, c + 1])
            queue.append([a + 1, b, c + 1])
 
c = int(input())
for _ in range(c):
    s, t = map(int, input().split())
    queue = deque()
    print(BFS())

 

 

 

이 정도까지일줄은 몰랐는데.. 확실히 BFS를 이용한 풀이가 백트래킹보다 빠른 것을 알 수 있었다.

 

 

---

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

14562번: 태권왕