[BOJ]1697 - 숨바꼭질 (Python)

문제 

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

코드 

from collections import deque
import sys
input = lambda : sys.stdin.readline().strip()


def bfs():
    queue = deque()
    queue.append(N)
    while queue:
        x = queue.popleft()
        if x == K:  # 해당 수에 도착
            print(visited[x])
            break
        for nx in (x - 1, x + 1, x * 2):
            if 0 <= nx < MAX and not visited[nx]:
                visited[nx] = visited[x] + 1
                queue.append(nx)


MAX = 100001
N, K = map(int, input().split())
visited = [0] * MAX
bfs()

 

풀이 

지난 주에는 행렬 관련 그래프 문제들을 풀다가 다시 일차원 배열 관련된 문제를 보니 접근하기 어려웠다.

아래 그림과 같이 배열을 그래프로 보는 방법은 누가 알려주었고, 생각의 방식을 바꾸니 해결책을 금방 생각해낼 수 있었다.  

이번에 배운 점 

 

• 런타임 에러가 날 수 있으므로 배열의 MAX값을 지정해주어야 한다 
• 항상!!! 범위 체크하는거 까먹지 말자