악곱 == 악성곱슬

BFS

---

해당 문제는 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후 인지 구하는 내용이다. 즉, 문제를 다시 보면 최소값을 구하는 문제이다.

해당 문제는 최소값을 구하는 문제인데, 그리디 알고리즘을 사용하여 구하려고 보니, *2연산과 +1연산, -1연산등 모두 겹쳐서 수행할 수 있는 연산들이었기 때문에 정당성을 확보할 수 없었다. 따라서 가까운 것 부터 탐색을 해보기 위해 BFS를 떠올렸다.

최소값을 구하기 위해서 3가지 가능한 이동을 queue에 넣으며 진행했다. level-order로 진행하기 때문에 먼저 방문한 노드는, 더 가까운 방법으로 도달할 수 있었다는 것이므로 제외시키며 진행했다.

코드는 아래와 같다.

import sys
from collections import deque

def bfs(start, target, visited):
    queue = deque()
    queue.append(start)
    visited[start] = 0
    while queue:
        cur = queue.popleft()
        # 현재 노드가 타겟 노드이면
        if cur == target:
            break
        # 이미 방문한 노드가 아니면 추가
        if cur - 1 >= 0:
            if visited[cur - 1] == -1:
                queue.append(cur-1)
                visited[cur-1] = visited[cur] + 1
        if cur + 1 < 100001:
            if visited[cur + 1] == -1:
                queue.append(cur + 1)
                visited[cur + 1] = visited[cur] + 1
        if cur * 2 < 100001:
            if visited[cur * 2] == -1:
                queue.append(cur*2)
                visited[cur*2] = visited[cur] + 1
    return visited[target]

def solution(n, k):
    visited = [-1] * 100001
    return bfs(n, k, visited)

if __name__ == "__main__":
    N, K = map(int, sys.stdin.readline().rstrip().split())
    print(solution(N, K))