[백준 1697] 숨바꼭질(python)

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

문제이해

수빈이의 위치에서 동생까지의 최단 거리를 구하는 문제

문제 포인트

1. 자신의 좌표로 부터 시작
2. 뒷 좌표는 볼 필요가 없음
3. 탐색이 진행되며 +1
4. 가장 먼저 도달한 node가 존재시에 break

실패 코드

import sys
from collections import deque

N, K = map(int, sys.stdin.readline().split())

matrix = [False] * 100000

matrix[N] = True

queue = deque()
queue.append((N, 0))

while queue:
    cur_position, cur_cnt = queue.popleft()

    moving = [-1, +1, cur_position]
    if cur_position == K:
        print(cur_cnt)
        break

    for i in range(3):
        next_position = cur_position + moving[i]

        if N < next_position <= 100000 and cur_position + cur_position < 100000:
            if not matrix[next_position]:
                matrix[next_position] = True
                queue.append((next_position, cur_cnt + 1))

cur_positon의 range를 정해주지 않았더니 최대 length를 벗어나서 발생하는듯함

수정 코드(정답)

import sys
from collections import deque

N, K = map(int, sys.stdin.readline().split())

matrix = [False] * 100001  # 0부터 100000까지 인덱스 사용

matrix[N] = True

queue = deque()
queue.append((N, 0))

while queue:
    cur_position, cur_cnt = queue.popleft()

    moving = [-1, +1, cur_position]
    if cur_position == K:
        print(cur_cnt)
        break

    for i in range(3):
        if i == 2:
            next_position = cur_position * 2
        else:
            next_position = cur_position + moving[i]

        if 0 <= next_position <= 100000 and not matrix[next_position]:
            matrix[next_position] = True
            queue.append((next_position, cur_cnt + 1))