백준 1967번(숨바꼭질) 파이썬

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

1697번: 숨바꼭질

지금까지 풀었던  bfs 문제와 유형이 달랐다.

지금까지는 좌표를 상하좌우로 이동하여 푸는 문제들이였는데 이 문제는

상하좌우가 아닌 -1,+1,*2 이 3가지의 방향으로 이동한다. 좌표도 필요가 없는 문제였다.

문제를 보고 그래프가 머리에 그려지긴 했지만 지금까지 풀던 문제와 달라 조금 당황했다.

그리고 시간초과가 나는 이유도 몰랐다가 다른 분들의 풀이를 참고해 이유를 알게되었다.

 

import sys
from collections import deque

input = sys.stdin.readline
max = 100001
N,K = map(int,input().split())
count = [0]*max #시간초과가 나지 않게 크기를 설정해준다.

def bfs(a,b):
    q=deque()
    q.append(a)
    
    while q:
        x = q.popleft()
        if x == b:
            print(count[x])
            break
        for dx in (x-1,x+1,x*2): # 방향이 3개이므로 for문을 이렇게 선언해준다.
            if (0<=dx<max and count[dx] == 0): # 리스트보다 크지않고 방문 안했을때!!
                q.append(dx)
                count[dx] = count[x]+1 # 반복될때마다 1씩 더해준다.

bfs(N,K)

아직 더... 해야 한다...