1697번 : 숨바꼭질 - Python

문제

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

풀이

BFS를 이용해서 x에서 갈 수 있는 곳을 다 가보면서 k인지 비교한다. 시간은 x에서의 시간 +1을 해주면 그게 x 다음번에 갈 곳에서의 시간이다.

코드

from sys import stdin
from collections import deque

input=stdin.readline

# 움직일수 있는 최대 좌표 100000
max_num=100000
visited=[0]*(max_num+1)

def bfs(k, n):
  q=deque()
  # 출발위치 큐에 삽입
  q.append(n)
  
  while q:
    x=q.popleft()
    
    # 위치가 동생의 위치와 같다면 종료
    if x==k:
        print(visited[x])
        break
   
    # 이동 할 수 있는 방향 정의
    for i in (x-1,x+1,x*2):
        #방문을 하지 않았고, 갈 수 있는 범위 내에 있는지 확인
        if 0<=i<=max_num and visited[i]==0:
            visited[i]=visited[x]+1
            q.append(i)

n,k=map(int,input().split())

bfs(k, n)

아쉬운 점

BFS문제인지도 모르고, 수학적으로 계산을 하다가 메모리 초과와 시간 초과를 보았다. 안풀린다면 답을 보는 것 보다. 알고리즘 분류를 본다음에 다시 한번 풀어봐야 겠다. BFS인지 전혀 감도 못잡았었다.