문제 (백준-1697 숨바꼭질)
출처 : https://www.acmicpc.net/problem/1697
문제는 위와 같습니다!
문제 이해
수빈이의 위치를 N, 동생의 위치를 K로 입력받습니다.
수빈이는 동생을 찾아야 합니다. 수빈이가 이동할 수 있는 방법은 2가지입니다.
-
수빈이가 걷는 방법 : N - 1, N + 1
-
수빈이가 순간이동하는 방법 : 2 * N
각 방법을 수행하는데 수빈이가 걸리는 시간은 1초 입니다.
구할것
- 수빈이가 동생을 찾는 최소의 시간을 구하면 됩니다!
문제 접근
수빈이가 움직일 수 있는 방법에 따라 바뀌는 수빈이의 위치는 3가지 입니다.
걷는 경우
N - 1을 1번
N + 1을 2번
순간이동하는 경우
2 * N을 3번
번호를 지정해 보았습니다.
수빈이의 위치가 바뀔 수 있는 경우는
1번 -> 2번 -> 3번
1번 -> 1번 -> 3번
2번 -> 2번 -> 2번
...
3번 -> 3번 -> 3번
솔직히 규칙은 찾아볼 수 없습니다.
위의 번호를 적은 이유는 1번의 경우든 2번의 경우든 3번의경우든 이동한 다음에는 어떤 방식으로든 이동할 수 있다는 것입니다.
트리의 방식으로 보면 트리의 깊이는 수빈이의 이동 횟수입니다.
처음 1번의 경우로 이동한 경우 1, 2, 3 모두이동할 수 있습니다.
결국 DFS탐색으로 생각을 했을 때 하나의 경우를 탐색하기 때문에 수빈이가 이동을 많이 할수록 탐색을 많이하게 됩니다.
위에서 트리의 깊이가 수빈이의 이동 횟수를 나타낸다고 했는데 우리가 구할것은 수빈이의 이동의 최소 시간입니다.
결국 수빈이가 가장 적게 이동하면서 동생을 찾는 것이기 때문에 DFS보다 BFS를 이용하는 것이 더 좋은 방법입니다.
코드
import sys
from collections import deque
input = sys.stdin.readline
# 수빈이의 위치
n, k = map(int, input().strip().split())
max_pos = 100001
# 수빈이가 여태껏 이동한 시간을 저장하는 배열
array = [0] * max_pos
def bfs(n):
queue = deque()
queue.append(n)
while queue:
now = queue.popleft()
if now == k:
return array[now]
next = now + 1
if next >= 0 and next < max_pos and array[next] == 0:
queue.append(next)
array[next] = array[now] + 1
next = now - 1
if next >= 0 and next < max_pos and array[next] == 0:
queue.append(next)
array[next] = array[now] + 1
next = 2 * now
if next >= 0 and next < max_pos and array[next] == 0:
queue.append(next)
array[next] = array[now] + 1
print(bfs(n))
후기
맨 처음에는 DP를 이용해서 해보려 했지만 도저히 규칙을 찾기가 어려웠습니다. 도저히 모르겠어서 문제 유형만 알자 생각하고 문제 태그를 확인하니 그래프탐색이었습니다.
DFS를 활용하려 하니 쉽지 않았고 그래프를 그려보니 BFS를 통해 해결하면 될것 같았습니다. 그래도 생각해서 푸니 정말 뿌듯했습니다!
