Baekjoon 1697번 숨바꼭질

문제

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

걸린 시간

02 : 57 : 24 실패

풀이

Python3

from collections import deque

if __name__ == "__main__":
    N, K = map(int, input().split())

    d = deque()        
    bound = 100000
    visited = [0]*(bound+1)
    t = 0

    visited[N] = 1
    d.append([N, 0])

    while d:
        X, t = d.popleft()

        if X == K:
            break

        t += 1

        if X-1 >= 0 and not visited[X-1]:
            visited[X-1] = 1
            d.append([X-1, t])

        if X+1 <= bound and not visited[X+1]:
            visited[X+1] = 1
            d.append([X+1, t])

        if X*2 <= bound and not visited[X*2]:
            visited[X*2] = 1
            d.append([X*2, t])

    print(t)

문제를 처음 읽었을 때 어떤 알고리즘을 사용해야 할지 전혀 감이 오질 않았다.

주어진 정보는 1차원 선 상에 놓인 수빈이와 동생의 위치 그리고 수빈이가 동생을 찾기 위해 이동할 수 있는 세가지 수단이 전부였기 때문이다.

글로만 봐선 특정 자료구조 형태를 띄고 있지 않지만 이 문제는 그래프 형태로 바꾸어 생각해 풀이해야한다. (어떻게?)

수빈이가 앞과 뒤로 걷거나 순간이동 하는 경우 모두 이동 비용이 1초로 동일하고, 동생을 찾을 수 있는 가장 빠른 시간을 구해야한다는 두가지 조건으로부터 그래프의 너비 우선 탐색(BFS)을 떠올릴 수 있다.

그림으로 과정을 그려가며 설명한 아래 링크의 풀이글이 이해하는데 많은 도움이 됐다.

참고

• BOJ 1697, 숨바꼭질 - 아테즈
• 백준 1697번 질문 - 반례가 뭐가 있을까요...? - qkrlwsnd