[알고리즘][Python] 백준(BOJ) 12851 숨바꼭질 2_파이썬

 

12851 숨바꼭질 2    https://www.acmicpc.net/problem/12851

12851번: 숨바꼭질 2

 

 

 

 

 

문제 풀기 전 공부할 것 : 그래프 탐색, 너비 우선 탐색

 

 

 

 

 

 

 

풀이

<내용>

• 수빈이(n)와 동생(k)의 위치를 입력받는다.
• 수빈이가 동생보다 오른쪽에 위치한다면(n >= k) -1을 수빈이와 동생의 위치 차이만큼 가는 방법 한 가지만 있다.
• 수빈이가 동생보다 왼쪽에 위치한다면 모든 경우를 따져봐야 한다.
  • check를 통해 수빈이가 각각 위치에 몇 번의 이동으로 도달할 수 있는지를 확인한다.

 

 

<코드>

from collections import deque

n, k = map(int, input().split())

def solve(n, k):
    if n >= k:
        print(n-k)
        print(1)
        return
    
    dx = [2, 1, -1]
    que = deque([(n, 0)])
    check = [0 for _ in range(100001)]
    count = 0
    while que:
        idx, cnt = que.popleft()
        if idx == k:
            if not check[idx]:
                check[idx] = cnt
                count += 1
            else:
                if cnt == check[idx]:
                    count += 1
                    
        for i in dx:
            if i == 2:
                new_idx = idx * i
            else:
                new_idx = idx + i
                
            if 0 <= new_idx <= 100000:
                if check[new_idx] == 0 or check[new_idx] >= cnt+1:
                    if check[k] and cnt+1 > check[new_idx]:
                        continue
                    check[new_idx] = cnt + 1
                    que.append((new_idx, cnt+1))
                
    print(check[idx])
    print(count)
    return

solve(n, k)