[BOJ 25418번] 정수 a를 k로 만들기(Python)

📝 문제

💡 입력으로 양의 정수 A와 K가 주어지면, 아래 연산을 이용하여 A를 K로 변경하려고 한다.
정수 A를 변경할 때 사용할 수 있는 연산 종류는 다음과 같다.

연산 1: 정수 A에 1을 더한다.
연산 2: 정수 A에 2를 곱한다.

정수 A를 정수 K로 만들기 위해 필요한 최소 연산 횟수를 출력하자.

⚙️ 입력 : 첫 번째 줄에 양의 정수 A와 K가 빈칸을 사이에 두고 순서대로 주어진다.

⚙️ 출력 : 첫 번째 줄에 양의 정수 A를 양의 정수 K로 만들기 위해 필요한 최소 연산 횟수를 출력한다.

 

문제링크

25418번: 정수 a를 k로 만들기

---

✅ 풀이

a, k = map(int, input().split())

visit = list()
visited = dict()

visit.append(a)
visited[a] = 0

while visit:

    node = visit.pop(0)
    if node == k:
        print(visited[node])
        break

    one = node + 1

    if one <= k and one not in visited.keys():
        visited[one] = visited[node] + 1
        visit.append(one)

    double = node * 2

    if double <= k and double not in visited.keys():
        visited[double] = visited[node] + 1
        visit.append(double)

💡 DFS를 사용하여 해결할 수도 있을 것 같아서 도전했는데, 재귀의 늪에 빠졌다.
빠르게 손절하고 BFS로 도망..
처음 입력받은 숫자인 a에서부터 출발한다.
딕셔너리인 visited에는 a까지 도달하는데 걸린 횟수인 0을 넣고 출발한다.

1만큼 이동하여 갈 수 있는 경우와 2배만큼 이동하여 갈 수 있는 경우를 고려하는데,
딕셔너리에 이미 해당 위치가 들어가있는 경우, 그 경우가 최소 횟수이므로 넘어간다.
그렇지 않은 경우는 이전 위치까지 가는 데 걸린 최소 횟수에 1을 더해 넣어준다.

그렇게 해서 a를 k로 바꾸는데 성공하면, k키의 값이 곧 최소 횟수가 된다.