문제:

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N()<=N<=100,000)에 있고, 동생은 점 K(0<=K<=100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다.

 

수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.

 

입력:

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

 

출력:

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

 

풀이 방법:

 여러 행위를 할 수 있는데 가장 빠른 방법을 찾는 문제는 대부분 BFS로 풀리는 경우가 많다. 따라서 이 문제도 X-1, X+1, 2X로 이동할 수 있는데 가장 빠른 시간을 찾기 때문에 BFS로 풀어야 한다.

 한 layer마다 Queue의 값에 따라 이동할 수 있는 위치를 새로 queue에 넣는다. 이 과정을 반복하다가 원하는 위치로 이동했다면(dist[k]의 값이 갱신 되었다면) queue를 종료하도록 해서 답을 출력하도록 했다.

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
import queue
n,k=map(int,input().split())
check=[0]*200000
dist=[0]*200000
check[n]=1
q=queue.Queue()
q.put(n)
while q.qsize():
    number=q.get()
    if number-1 >=0:
        if check[number-1]==0:
            q.put(number-1)
            check[number-1]=1
            dist[number-1]=dist[number]+1
    if number+1 < 200000:
        if check[number+1]==0:
            q.put(number+1)
            check[number+1]=1
            dist[number+1]=dist[number]+1
    if 2*number < 200000:
        if check[2*number]==0:
            q.put(2*number)
            check[2*number]=1
            dist[2*number]=dist[number]+1
    if dist[k]:
        break
print(dist[k])
cs

 

문제 링크:

https://www.acmicpc.net/problem/1697

'Algorithm > Python' 카테고리의 다른 글

[BOJ]1759. 암호 만들기  (0) 2019.09.24
[BOJ]14889. 스타트와 링크  (0) 2019.09.23
[BOJ]2022. 사다리  (0) 2019.09.21
[BOJ]1561. 놀이공원  (0) 2019.09.20
[BOJ]1080. 행렬  (0) 2019.09.19

+ Recent posts