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

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

12851번: 숨바꼭질 2

Problem

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

조건

• 첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.
• 첫째 줄에 수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.
• 둘째 줄에는 가장 빠른 시간으로 수빈이가 동생을 찾는 방법의 수를 출력한다.

SOL

방문한 곳을 또 방문할 수 있다는 조건을 처리를 해주지 않아서 틀렸던 문제이다!

 

import sys
from collections import deque
from collections import defaultdict
N,M=map(int,input().split())

visited= [0 for _ in range(100001)]
count = defaultdict(int)

def bfs(start):
	dq=deque()
	visited[start]=1
	dq.append(start)
	while dq:
		x=dq.popleft()
		if x==M:
			count[x] +=1
		for nx in [x-1,x+1,2*x]:
			if not 0<=nx<100001:
				continue
			if not visited[nx] or visited[nx]>=visited[x] +1 :
				visited[nx]= visited[x] +1
				dq.append(nx)

bfs(N)
print(visited[M]-1)
print(count[M])