[백준] 1697 : 숨바꼭질 / python

1. 문제 설명

1697번: 숨바꼭질

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고,

동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다.

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

순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다.

수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하기

입력

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

출력

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

 

2. 풀이 전 계획과 생각

4초

5 → 10 → 9 → 19 → 7

 

3. 풀이하면서 막혔던 점과 고민

🤔 무조건 2배 해준다고 좋은 것이 아니다. 모든 경우의 수를 다 따져야 한다.

하지만 입력값이 너무 크다. 어떻게 하면 좋을까?

 

💡  모든 경우를 탐색해야 하고, 최단 시간을 구하기 위해, BFS를 사용 하려고 한다.

 

🤔  그런데, Graph가 주어져있지 않다.

주어진 정보들을 가지고 정점과 간선을 정의해볼 수 있을까?

• 정점
  • 점의 번호가 곧 정점의 번호
• 간선
  • 이동을 의미하는 것을 간선으로 표현
  • 각 점마다 -1, +1, *2인 점을 향하는 방향성 간선

간선 하나를 타고 이동 = 1초 동안 이동

가장 빠른 시간에 동생 찾는다는 것 = 최소 갯수로 간선 이동

BFS로 최단 경로를 찾자.

 

3. 풀이

import sys
from collections import deque

input = sys.stdin.readline

N, K = map(int, input().split())
visited = [-1] * 100001

queue = deque()
queue.append(N)
visited[N] = 0

while queue:
    pos = queue.popleft()
    if pos == K:
        print(visited[pos])
        break

    for next_pos in (pos -1, pos + 1, pos * 2):
        if 0 <= next_pos < len(visited) and visited[next_pos] == -1:
            queue.append(next_pos)
            visited[next_pos] = visited[pos] + 1

 

4. 풀이 후 알게된 개념과 소감

• 여러 곳으로 이동할 수 있음으로, (= 여러 vertex로 이동할 수 있음으로 = 여러 edge들이 있음으로)
  하나의 그래프로 볼 수 있다.