문제:

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 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

+ Recent posts