코드

from collections import deque

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

# 문제에서 제시해준 n, k의 최대 범위 => 10만
ran = 100001

# 출발점에서 인덱스에 해당하는 위치까지의
# 최소 이동 횟수를 담을 리스트
visited = [0] * ran

def bfs():
    q = deque()
    q.append(n)
    
    while q:
        # 수빈이 현재 위치
        x = q.popleft()
        
        # 동생의 위치와 수빈이의 위치가 같다 => 찾았다
        if x == k:
            print(visited[x])
            break
            
        # 걸을 때 움직일 수 있는 위치 (+1, -1)
        # 순간이동할 때 움직일 수 있는 위치 (x2)
        # 세 경우를 모두 찾아줌
        for i in (x-1, x+1, x*2):
            
            # 위의 3가지 경우 중
            # 문제의 조건에 해당하는 범위만 탐색
            if 0 <= i < ran and not visited[i]:
                visited[i] = visited[x] + 1
                q.append(i)
             
bfs()

문제 해설

숨바꼭질

BFS 문제이다. 위의 그림처럼 수빈이가 이동할 수 있는 모든 거리에 대하여 그래프를 만든 후, 동생이 있는 위치가 나올 때까지 탐색해준다. (문제의 힌트에서 힌트가 5-10-9-18-17로 되어있는데, 순차적으로 탐색하는 경우 5-4-8-16-17이 가장 빠른 방법인듯)

문제 풀이에 대한 경험치가 매우 중요하다고 느낀 문제… 반복적으로 나오는 좌표값이 존재하길래 DP로 접근하려다가 도무지 어떻게 점화식을 작성해야 하는지 모르겠어서 그림을 그려보니 그래프가 보여서 BFS로 접근하고 구글링을 참고하여 정답을 제출하였다.

댓글남기기

참고