[실버 1] 1697번: 숨바꼭질

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

1697번: 숨바꼭질

---

문제

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다.

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

입력

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

출력

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

---

사고의 흐름

• 뭔가 그리디스러운 문제인데?
• 만약 동생의 위치가 수빈이의 위치보다 앞에 있으면 수빈이는 선택의 여지가 없이 계속 걸어가야 한다. 순간이동으로는 뒤로만 갈 수 있기 때문이다.
• 만약 동생의 위치가 수빈이의 위치보다 뒤에 있으면 N이 0이 아닐 때 최대한 순간이동을 많이 하면 된다. 무조건 순간이동이 걷는 것보다 빠르기 때문이다.

 

• 그리디가 아니었다. 동생의 위치가 수빈이의 위치보다 뒤에 있을 때 무조건 동생의 앞쪽에서 접근할 필요는 없다. 동생의 뒤로 순간이동 한 다음 앞쪽으로 이동해도 되기 때문이다.
• BFS로 푸는 것이 맞는다.

내가 작성한 소스코드

import sys
from collections import deque


def bfs(start, end, cnt_moves):
    q = deque()
    q.append(start)
    cnt_moves[start] = 0

    while q:
        cur = q.popleft()

        if cur == end:
            print(cnt_moves[cur])
            sys.exit(0)

        if cur-1 >= 0:
            if cnt_moves[cur-1] == -1:
                q.append(cur-1)
                cnt_moves[cur-1] = cnt_moves[cur] + 1

        if cur+1 <= 100000:
            if cnt_moves[cur+1] == -1:
                q.append(cur+1)
                cnt_moves[cur+1] = cnt_moves[cur] + 1

        if cur*2 <= 100000:
            if cnt_moves[cur*2] == -1:
                q.append(cur*2)
                cnt_moves[cur*2] = cnt_moves[cur] + 1


cnt_moves = [-1] * 100001
n, k = map(int, sys.stdin.readline().split())
bfs(n, k, cnt_moves)

남이 작성한 소스코드

bomul1128 님:
https://www.acmicpc.net/source/38017330

피드백

• 그리디는 그리디 문제를 해결하는 방법을 아는 것도 중요하지만, 그리디 문제가 아닌 문제를 그리디로 착각하지 않는 것이 제일 중요하다.
• Indexing하려는 Index가 범위를 벗어나지 않았는지 체크할 것.
• Module을 Import할 때 as "" 를 사용하면 별명을 지정할 수 있다.
• 이 문제는 최적 부분 구조(Optimal Substructure)와 중복되는 부분 문제(Overlapping Subproblem)을 충족하므로 Top-down 방식의 재귀로 해결할 수 있다. 즉 N < K 일 때 ,현재 위치가 짝수이면 현재 동생의 위치를 2로 나눈 점을 이전 위치로 잡은 뒤 이전 위치에서 순간이동을 하는 경우와 그냥 걸어오기만 하는 경우의 움직임 횟수를 비교해 더 작은 횟수에 1을 더하면 된다. 만약 현재 동생의 위치가 홀수라면 앞의 위치와 뒤의 위치에서의 움직임 횟수를 비교한 다음 더 작은 횟수에 1을 더한다.