문제:
수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다.
수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.
입력:
첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.
출력:
첫째 줄에 수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.
둘째 줄에 어떻게 이동해야 하는지 공백으로 구분해 출력한다.
풀이방법:
https://www.acmicpc.net/problem/12851
12851번: 숨바꼭질 2
수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때
www.acmicpc.net
2022.08.09 - [Algorithm/Python] - [BOJ]12851. 숨바꼭질 2
이전 문제의 발전된 버전으로 가장 빠른 시간과 그 시간으로 이동한 경로를 출력해야 하는 문제다. 위 문제 해결 방법에 추가적으로 visited 배열을 이전에는 0과 1의 여부로만 사용했지만 count 값을 저장하도록 하여 최소 시간을 측정할 수 있도록 했다. 그리고 path라는 배열을 사용해서 이동한 점의 위치에 기존에 있었던 점의 값을 저장하도록 하여, 동생이 위치한 점에 도달했을 때, 역추론이 가능하도록 한다.
역추론을 하기 위한 print_path라는 함수가 존재하며 history를 만든 후 이를 뒤집어서 출력하도록 한다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
|
from collections import deque
def print_path(now):
history = []
temp = now
for _ in range(visited[now]+1):
history.append(temp)
temp = path[temp]
print(" ".join(map(str, history[::-1])))
N, K = map(int,input().split())
visited = [0]*100001
path = [0]*100001
queue = deque([[N, 0]])
while queue:
point, count = queue.popleft()
if point==K:
print(visited[point])
print_path(point)
break
if point-1>=0 and not visited[point-1]:
queue.append([point-1,count+1])
visited[point-1]=count+1
path[point-1] = point
if point+1<=100000 and not visited[point+1]:
queue.append([point+1,count+1])
visited[point+1]=count+1
path[point+1] = point
if 2*point<=100000 and not visited[2*point]:
queue.append([2*point,count+1])
visited[2*point]=count+1
path[2*point] = point
|
cs |
문제링크:
https://www.acmicpc.net/problem/13913
13913번: 숨바꼭질 4
수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일
www.acmicpc.net
'Algorithm' 카테고리의 다른 글
| [BOJ]11559. Puyo Puyo (0) | 2021.09.07 |
|---|---|
| [BOJ]3190. 뱀 (0) | 2021.08.19 |
| [BOJ]1520. 내리막길 (0) | 2021.08.17 |
| [BOJ]1987. 알파벳 (0) | 2021.08.10 |
| [BOJ]14425. 문자열 집합 (0) | 2021.06.24 |