[백준] 13549번 숨바꼭질 3 [Python] - 데이크스트라

 

 

N을 아래 연산을 통해서 K로 바꾸는 데 걸리는 시간을 구하는 문제

연산 : 소요 시간

+1 또는 -1 : 1초

x2$($2배$)$ : 0초

 

문제

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

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

입력

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

출력

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

 

N -> K의 과정 대신 2배 연산을 나누기 2 연산으로 바꾸어서 K -> N 문제로 바꾸어 코드를 작성했습니다.

 

• N이 K보다 크다면 -1 연산만 최소 시간을 구할 수 있는 연산입니다.
• N이 0이라면 잠시 N -> K 과정이라고 생각하고 +1 연산을 하고 1초를 추가한 후 K -> 1 과정을 생각합니다.
• K가 짝수라면 2배 연산을 했을 수 있으므로 반대로 나우기 2연산을 할 수 있습니다.
  • -1 연산과 나누기 2 연산의 소요 시간을 비교해서 최소 값을 구합니다.
• 0 < N < K 이고 K가 홀수이면. +1 또는 -1 연산으로 1초를 추가한 뒤,
  K-1 -> N 과 K+1 -> N 중에서 최소 소요 시간을 구합니다.

 

DFS

from sys import stdin
input = stdin.readline

def dfs(N, K):
    if N >= K:  return N-K
    if not N: return 1 + dfs(1, K)
    if not K%2: return min(K-N, dfs(N, K//2))
    return 1 + min(dfs(N, K-1), dfs(N, K+1))

def main():
    N, K = map(int, input().split())
    print(dfs(N,K))

if __name__ == "__main__":
    main()

 

 

BFS

from sys import stdin
input = stdin.readline

def main():
    N, K = map(int, input().split())
    if N >= K: 
        return N-K
    q = [(K, 0)]
    v = set()

    while True:
        s, t = q.pop(0)
        if s == N:
            return t
        if not s%2 and (d:=s//2) not in v and s > N:
            v.add(d)
            q.append((d, t))
        for i in (s+1, s-1):
            if i not in v and i < K+2:
                v.add(i)
                q.append((i, t+1))

if __name__ == "__main__":
    print(main())

 

예제 입력 1 

5 17

예제 출력 1 

2

힌트

수빈이가 5-10-9-18-17 순으로 가면 2초만에 동생을 찾을 수 있다.