https://www.acmicpc.net/problem/12851
12851호 숨바꼭질 2
수빈은 남동생과 숨바꼭질을 하고 있다. 수빈은 현재 포인트 N(0 ≤ N ≤ 100,000)에 있고, 동생은 포인트 K(0 ≤ K ≤ 100,000)에 있다. 수빈은 걷거나 텔레포트할 수 있다. 수빈의 위치가 X라면
www.acmicpc.net
경로의 수를 찾는 문제
import sys
import collections
sys.stdin = open('C:/Users/USER/Desktop/vs/py/py1/input.txt', 'r')
def input():
return sys.stdin.readline().strip()
# ==================================================================================
N, K = map(int, input().split())
visited = (-1 for i in range(100001))
visited(N) = 0
q = collections.deque()
q.append(N)
while q: #BFS
pos = q.popleft()
if pos == K: #K에 도달하면 break
break
pos_list = (pos+1, pos-1, pos*2) #갈 수 있는 방향
for i in pos_list:
if 0 <= i <= 100000: #범위 안이면
if visited(i) == -1: #방문하지 않았던 곳이면
q.append(i) #큐에 i push
visited(i) = visited(pos)+1
path = 0 #경로 수
q = collections.deque()
q.append(K)
while q: #BFS
n = q.popleft()
if n == N: #N에 도달하면 path +1
path += 1
else:
if n % 2 == 0: #짝수면 세 방향으로 되돌아갈 수 있음
n_list = (n+1, n-1, n//2)
else: #홀수면 두 방향으로 되돌아 갈 수 있음
n_list = (n+1, n-1)
for i in n_list:
if 0 <= i <= 100000: #범위 안일 경우만
#되돌아간 곳의 시간이 지금보다 -1 이면 현재까지는 옳은 경로
if visited(i) == visited(n)-1:
q.append(i) #i 추가
print(visited(K)) #걸리는 시간
print(path) #경로 수BFS를 두 번 사용하여 해결
왔던 길을 되돌아가면서 시간이 맞는지 확인하는 메소드를 작성했습니다.
