[Python] 백준 1697번 숨바꼭질 - 차근차근 문제접근

숨바꼭질 성공

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
2 초	128 MB	147202	41776	26180	25.026%

문제

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 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초만에 동생을 찾을 수 있다.

문제 풀이

1. 처음 수빈이의 위치 N 에서 동생의 위치 K로 가는 최단 시간을 찾는 것이다.
2. 최단 시간을 찾는 것이기에 DFS, BFS를 먼저 생각할 수 있다.
3. 기존 위치에서 이동하는 위치는 3가지 X - 1, X + 1, 2 x X 로 총 3가지가 있다. 즉 노드가 3개로 펼쳐져 나갈 수 있다.
4. 하나의 노드가 얼마나 깊이까지 가는지 모두 확인해서 최단시간을 찾으려면 모든 경로를 다 탐색해야하므로 비효율적이다. 즉 DFS 보다는 BFS 임을 생각한다. 동일 시간 내에서(동일 그래프 깊이) 가장 먼저 도착하는 경우가 생겼을 때가 최적 시간임을 알 수 있다.
5. BFS로 문제를 풀기로 했으니, 기존 BFS 코드를 작성한다.
6. 다음 노드로 펼쳐져 가는 것이 3가지가 있으니 Queue에 append할 아이템이 3가지이다.
7. 최대, 최소 값이 존재하므로 X - 1, X + 1, 2 x X 값이 범위를 넘어가지 않도록 조건문을 사용해준다.
8. 방문 위치를 표시하기 위한 방법을 생각해 Array 하나를 만들어 준다.
9. 각 방문에 대한 표시를 노드 깊이로 설정하면, 해당 위치까지 걸린 시간을 대표하는 값이기도 하다.
10. 해결

소스코드

import sys
from collections import deque

def bfs(v):
    q = deque([v])
    while q:
        v = q.popleft()
        if v == k:
            return array[v]
        for next_v in (v-1, v+1, 2*v):
            if 0 <= next_v < MAX and not array[next_v]:
                array[next_v] = array[v] + 1
                q.append(next_v)


MAX = 100001
n, k = map(int, sys.stdin.readline().split())
array = [0] * MAX
print(bfs(n))

출처

백준

Olympiad > USA Computing Olympiad > 2006-2007 Season > USACO US Open 2007 Contest > Silver 2번