14562. [Python]태권왕

1. 문제

 

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

 

 

2. 접근 방법

 

• 시간 제한: 2초
• 메모리 제한: 128MB
• 그래프 이론
• 너비 우선 탐색

 

3. 파이썬 코드

 

import sys
from collections import deque
# BFS 통한 탐색
def BFS(start,target):
    # 초기값으로 시간, 시작점, 목표점
    q = deque([(0,start,target)])
    while q:
        time, current, target = q.popleft()
        # 현재 점수가 목표점수와 같은 경우
        if current == target:
            # 시간 출력
            print(time)
            break
        # 목표점수 + 3 의 값보다 현재값의 2배한 값이 작거나 같은경우
        if target + 3 >= current*2:
            # 점수가 한번도 횟수가 안나온 경우
            if graph[current*2] == -1:
                # queue 값에 현재 시간 +1, 현재점수 *2, 목표점수 +3 추가
                q.append((time+1, current*2, target+3))
        # 만약 현재 점수 +1 한 값이 나오지 않은 점수인 경우
        if graph[current+1] == -1:
            # queue 에 현재 시간 +1, 현재 값 +1, 목표값 저장
            q.append((time+1, current+1, target))

input = sys.stdin.readline

T = int(input())

for tc in range(T):
    graph = [-1] * 100001
    me, enemy = map(int,input().split())
    if me == enemy:
        print(0)
        continue
    BFS(me,enemy)

 

4. 문제를 풀고난 후 생각

 

• 숨바꼭질 문제와 비슷한 유형의 문제로 현재 점수를 바탕으로 목표 점수와 횟수를 체크하여 너비 우선탐색을 진행하여 목표점수에 도달했을 경우 걸린 횟수를 출력해주는 문제이다.
• 점수의 - 값이 없기 떄문에 *2 를 한 값이 목표점수 +3 보다 큰 경우는 queue에 추가하지 않는 경우를 조건에 넣어주면 탐색이 오래걸리지 않는다.
• 점수가 초기값이 100보다 작거나 같다고 나왔지만 실제 점수의 최대값은 정해져있지 않기 떄문에 넉넉하게 graph 값을 100001 로 초기값으로 잡아줘서 IndexError 를 방지했다.

 

5. 문제를 푸는데 도움이 되는 지식

 

• 너비 우선 탐색(BFS)