[백준 12851번] 파이썬 - 숨바꼭질2

http://www.acmicpc.net/problem/12851

12851번: 숨바꼭질 2

 

 

# 조건

• 수빈이는 동생과 숨바꼭질을 하고 있다.
• 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다.
• 수빈이는 걷거나 순간이동을 할 수 있다.
  • 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다.
  • 순간이동을 하는 경우에는 1초 후에 2 * X의 위치로 이동하게 된다.
• 수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지
• 그리고, 가장 빠른 시간으로 찾는 방법이 몇 가지 인지 구하는 프로그램을 작성하시오.

 

# 접근 방법

• 너비 우선 탐색을 통하여 구해주면 된다.
• bfs에 deque를 선언해주고, 현재 위치를 담아준다.
• 또한, 방문 기록 -> 현재 움직인 횟수 로 담아주며
• 도착지에 도착한 경우 최소값이 동일하다면 카운트 해준다.
• bfs 함수내에서 for문의 순회 리스트를 -> x-1, x+1, 2 * x로 해준다.
• 이미 방문한 곳이더라도, 현재 거리가 최소거리라면 q에 추가해준다.
  • 이걸 판별하기 위해 다음 위치 = 현재위치 +1 이라면
  • q에 추가해주었다.

import sys  
sys.stdin = open('input.txt')  
input = sys.stdin.readline  
from collections import deque  
  
def bfs(start):  
    global cnt  
    visited = [0] * 100001  
    visited[start] = 1  
    q = deque([N])  
    while q:  
        loc = q.popleft()  
        if loc == K:  
            cnt += 1  
        for i in [loc+1, loc-1, loc*2]:  
            if 0 <= i <= 100000:  
                if not visited[i] or visited[i] == visited[loc]+1:  
                    q.append(i)  
                    visited[i] = visited[loc] + 1  
  
    return visited  
N, K = map(int, input().split())  
cnt = 0  
arr = bfs(N)  
print(arr[K]-1)  
print(cnt)