1. 문제 설명
수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 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들이 있음으로)
하나의 그래프로 볼 수 있다.
'Problem Solving' 카테고리의 다른 글
[백준] 10815 : 숫자 카드 / python (0) | 2022.02.13 |
---|---|
[백준] 13549 : 숨바꼭질3 / python (0) | 2022.02.13 |
[프로그래머스] 튜플 (2019 KAKAO INTERNSHIP) / python (0) | 2022.02.06 |
[백준] 1753 : 최단경로 / python (0) | 2022.02.05 |
[백준] 18352 : 특정 거리의 도시 찾기 / python (0) | 2022.02.03 |