백준 1697번: 숨바꼭질 (S1) - Python 풀이

문제 설명

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

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다.

만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다.
순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다.

수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.

입력

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

출력

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

예제 입력 1

5 17

예제 출력 1

4

힌트

수빈이가 5-10-9-18-17 순으로 가면 4초만에 동생을 찾을 수 있다.

풀이 과정

N에서 K를 만날 때까지 탐색해야 합니다. 일단 이동 방식은 +1, -1, *2로 3가지가 존재하고, 3가지의 방식 모두 가중치는 1로 동일하게 측정됩니다. 이때 누적 가중치의 최솟값를 구하는 문제이기 때문에, ‘가중치가 동일할 때의 최단거리를 구할 때 사용하는’ BFS 알고리즘을 사용하면 된다는 것을 알 수 있습니다.

N에서부터 각 위치까지의 최단 거리를 저장하는 배열이 필요합니다. 상하좌우 이동이었다면 2차원 배열을 사용했겠지만 +1, -1, *2로의 이동만 존재하기 때문에 1차원 배열을 사용합니다. 2차원 배열에서 상하좌우 이동 시 dx, dy 값에 맞게 for문을 4번 돌리는 것처럼, 이 문제에서는 이동할 수 있는 루트가 3가지이기 때문에 for문을 3번 돌립니다.

BFS는 시작 노드로부터 가까운 노드를 먼저 방문하고, 멀리 떨어진 노드는 그 이후에 방문하는 순서로 진행됩니다. 이 과정에서 한 번 방문한 노드는 다시 방문하지 않는다면, K에 위치한 노드를 방문했을 때의 가중치는 K까지의 최단 거리를 보장합니다. 1차원 배열의 크기는 N과 K의 최댓값인 100000을 모두 담을 수 있게 100001로 설정하지만, K 위치의 최단 거리까지만 찾으면 더 이상의 탐색을 하지 않고 종료합니다.

정답 코드

from collections import deque

N, K = map(int, input().split())

# N에서 시작해서 K까지의 최단거리를 구하기 위한 BFS
def BFS(N, K):
    # 시작점과 도착점이 같으면 0 반환하고 종료
    if N == K:
        return 0
    
    # N에서부터 각 위치까지의 최단 거리를 저장하는 1차원 배열 생성
    # 0으로 초기화 하고 아래 반복문에서 순차적으로 업데이트 된다
    distances = [0] * 100001
    # 큐에 시작점 N을 넣고 시작
    queue = deque([N])
    
    # 큐가 빌 때까지 반복
    while queue:
        # 큐의 맨 앞에 있는 위치 now를 꺼낸다
        now = queue.popleft()
        # now의 왼쪽, 오른쪽, 2배한 위치를 모두 확인
        for next_pos in (now-1, now+1, now*2):
            # 배열의 범위이고, 아직 방문한 적이 없으면
            if 0 <= next_pos <= 100000 and distances[next_pos] == 0:
                # next_pos까지의 최단 거리를 현재 위치 now까지의 최단 거리에 + 1한 값으로 업데이트
                distances[next_pos] = distances[now] + 1
                # next_pos가 K라면
                if next_pos == K:
                    # 더 이상 탐색할 필요없이 이 위치의 최단 거리를 반환하고 종료
                    return distances[next_pos]
                # 아직 K까지 못 왔으면 next_pos 위치를 큐에 넣고 이어서 탐색
                queue.append(next_pos)

print(BFS(N, K))

이상입니다.