(Python/🥈1)백준 알고리즘 1697번: 숨바꼭질

728x90

문제 출처: https://www.acmicpc.net/problem/1697

1697번: 숨바꼭질

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일

www.acmicpc.net

풀이:

import sys
from collections import deque
sys.stdin = open('/Users/song/Desktop/Python/Python/h.txt', 'r')



def bfs(v):
    Q = deque([N])
    while Q:
        v = Q.popleft()
        if v == M :
            return visited[v]

        for next_v in (v-1, v+1, 2*v):
            if 0 <= next_v <= 100000 and not visited[next_v]:
                visited[next_v] = visited[v] + 1
                Q.append(next_v)
N,M = map(int,input().split(" "))
visited = [0] * 100001
print(bfs(N))

처음엔 백트래킹을 사용해서 풀려고했지만 대 실패

bfs풀이

visited 100000 개 0 으로 만들고

시작 지점 N 을 Q 에 넣는다

Q에서 뽑았을때 도착지와 같으면 return

갈수 있는 방향은 Q에서 뽑은 v 에서 -1,+1,*2 한 곳을 갈수 있다.

방문하지 않은곳이여야하고 0이상 10만 이하여야한다.

이 전 미로 문제처럼 +1 해준다