[Python] 1697 - 숨바꼭질

1. 문제 정의

수빈이와 동생의 위치가 각각 주어지고, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간을 출력하는 프로그램을 작성하는 문제이다.

 

2. 풀이 방식

입력으로 수빈이의 위치(N)과 동생의 위치(K)를 받는다.

이후 각 점에 대해 방문 횟수를 남기기 위해 리스트를 생성한다.

 

현재 위치에서 다음 위치로 이동하는 경우의 수를 따로 정의하지 않고, 반복문 내부에서 정의하였다.

다음 위치가 범위(0 ~ 100,000)를 만족하고, 방문 횟수가 0회(방문 X)인 경우 (현재 위치의 방문횟수 + 1)을 해준다.

이후 Q에 추가하여 다음 탐색 대상으로 지정한다.

 

현재의 위치와 동생의 위치가 같으면 함수의 return으로 현재 위치를 넘겨준다.

from collections import deque
import sys

input = sys.stdin.readline

MAX = 10 ** 5 # 입력의 최댓값

N, K = map(int, input().split())
dist = [0] * (MAX + 1) # 방문 표시 및 당시의 거리

def bfs(num):
    Q = deque()
    Q.append(num) # 처음 위치

    while Q:
        c = Q.popleft()

        if (c == K): # 현재 위치가 K와 일치하다면
            return dist[c] # 방문 횟수 리턴

        # 현재 위치에서 다음 위치로 이동하는 경우의 수
        for ix in (c-1, c+1, c*2):
            if (0 <= ix <= MAX) and (dist[ix] == 0): # 다음 위치가 범위에 있고 방문하지 않았더라면
                dist[ix] = dist[c] + 1 # 방문횟수 1 증가
                Q.append(ix) # 큐에 입력해주어 다음 탐색에 이용

print(bfs(N)) # 출력

 

3. 후기

현재 정점에서 다음 정점으로 이동하는 모든 경우를 카운트하여 하나의 리스트에 저장하는 방식으로 해결하였는데, BFS로 탐색하여 모든 경우를 탐색하여 그 중 최솟값을 찾는 완전 탐색과 비슷한 느낌의 문제였던 것 같다.

 

이 문제를 풀다 안 사실인데, 함수의 return값이 출력값이 되는 줄 알았더만, 실제로는 print문에 의해 출력이 이루어져야 완벽한 출력으로 인식이 된다더라..

 

IDE에서는 그냥 함수만 호출해도 함수의 return값이 출력으로 나오지만, 백준 등 프로그래밍 테스트 사이트에서는 정확하게 print문을 이용하여 출력을 확실하게 해주어야 한다고 한다.