문제

입력

첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.

출력

수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.

입력 예시 1

5 17

출력 예시 1

4

문제 이해

이 문제가 DFS/BFS 유형인걸 알고 문제를 봤다. 근데 이 문제를 그래프탐색으로 풀 수 있는 문제인가? 라는 생각이 먼저 들었다. 그냥 수식을 따로 만들어서 풀어야 할줄 알았는데 BFS의 원리를 잘 몰라서 그렇게 생각한 것 같다. 이동을 어떻게 하든지 BFS를 사용하면 최단거리를 구할 수 있는 것 같다. 아직은 BFS를 더 공부해야 할 것 같다.

문제는 현재 위치에서 -1, +1 *2를 해주면서 도착지점까지 몇번 움직였는지 출력하면 된다. 어렵지는 않은데 풀이를 떠올리는게 어려운 것 같고, 방향벡터를 다른 방식으로 구현하는게 신선한 문제였다.

코드

# 백준 1697번 숨바꼭질

import sys
input = sys.stdin.readline

from collections import deque

def BFS(x):
    global visited
    time = 0
    queue = deque()
    queue.append((x, time))

    while queue:
        x, time = queue.popleft()
        if x == K:
            print(time)
            return

        for nx in [x-1, x+1, 2*x]:
            if 0 <= nx < 100000 + 1 and not visited[nx]:
                queue.append((nx, time + 1))
                visited[nx] = True


# 0. 입력 및 초기화

# N:수빈 위치, M:동생 위치
N, K = map(int, input().split())
visited = [False] * (100000 + 1) # 맵이자 방문여부 확인 리스트

# 1. BFS호출 및 출력
BFS(N)

알아야할 스킬셋

for 반복문에서 리스트를 참조하기

for nx in [x-1, x+1, 2*x]:
            if 0 <= nx < 100000 + 1 and not visited[nx]:
                queue.append((nx, time + 1))
                visited[nx] = True

원래 상하좌우로 이동하는 시뮬레이션 DFS/BFS 문제에서는 방향벡터를 리스트로 구현을 하고 "nx = x + dx[i]" 같이 구현을 하는데 이 문제는 세번째 리스트가 곱셈이라서 한 수식으로는 표현이 힘들다. 그래서 이런 문제는 리스트 자체를 만들어서 참조할 수 있다. 만들어놓은 리스트의 이름만 가져오는게 아니라 이름 없는 리스트를 만들어서 참조하면 된다. 처음보고 되게 신기했던 방식이다.