[BOJ] 16953번 파이썬 - A → B

seon·2025년 5월 9일

알고리즘

Algorithm

목록 보기

40/41

문제

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

*️⃣1차 시도

import sys
input = sys.stdin.readline

A, B = map(int, input().split())
cnt = 0

while cnt > 0:
  if B % 2 == 0:
    B = B // 2
    cnt += 1
  elif str(B)[-1] == '1':
    B = int(str(B)[:-1])
    cnt += 1
  else:
    cnt = -1
  if B == A:
    break

print(cnt)

틀린 이유 1: while cnt >0 라는 조건은 루프가 시작도 하지 않게 만든다. cnt는 처음에 0으로 초기화되는데, cnt > 0이면 루프가 한 번도 실행되지 않는다.
해결 방법: 조건을 while B > A로 바꿔야 한다. 왜냐하면 B를 줄여가며 A로 만드는 방식이기 때문이다.

틀린 이유 2: B == A일 때 cnt가 정확히 계산되지 않는다.
cnt를 증가시키는 위치와 순서가 애매해서, 최종적으로 연산 횟수를 정확히 출력하지 못한다. 문제에 따르면 “연산 횟수 + 1”을 출력해야 한다.
해결 방법: cnt 초기값 cnt = 1로 설정

*️⃣2차 시도

import sys
input = sys.stdin.readline

A, B = map(int, input().split())
cnt = 1

while B != A:
  if B < A:
    cnt = -1
    break
  if B % 2 == 0:
    B = B // 2
  elif B % 10 == 1:
    B = B // 10
  else:
    cnt = -1
    break
  cnt += 1

print(cnt)

결과

*️⃣다른 풀이

출처: https://mi-dairy.tistory.com/entry/Python-16953%EB%B2%88-A-%E2%86%92-B

*️⃣ 전체 코드

from collections import deque

a, b = map(int, input().split())
graph = {}

def bfs(v):
    q = deque([v])         # 시작 노드 큐에 넣기
    graph[v] = 0           # 시작 노드는 연산 횟수 0
    while q:
        node = q.popleft()  # 현재 노드 꺼내기

        if node == b:       # 목표 도달했으면 연산 횟수+1 반환
            return graph[node] + 1
        for next_node in (2*node, int(str(node)+'1')):
            if next_node <= b and next_node not in graph:
                graph[next_node] = graph[node] + 1
                q.append(next_node)
    return -1
 
print(bfs(a))

BFS를 이용한 풀이.
해당 알고리즘을 사용하는 이유:
BFS(너비 우선 탐색) 알고리즘은 최단 거리(최소 연산 횟수)를 구하는 데 적합한 알고리즘이다.
위 문제는 A에서 B로 가는 최소 연산 횟수를 구해야 하므로 BFS를 이용하여 풀 수 있다.

이 문제는 일종의 그래프 탐색 문제로 생각할 수 있다.
각 정수(노드)에서 다음 가능한 수들로 연결된 간선이 있다고 보면 된다.

참고 링크

파이썬으로 그래프 구현하기

파이썬 자료구조

"위 링크의 내용은 Algorithm, Language 시리즈에 따로 정리해놓았습니다!"

*️⃣ 코드 한 줄씩 설명

from collections import deque

deque는 BFS에서 사용하는 큐 자료구조이다. 빠른 pop(0)을 위해 사용한다.

a, b = map(int, input().split())
graph = {}

a, b는 시작 & 목표 수
graph는 각 숫자까지 도달하는 데 걸린 연산 횟수를 저장하는 딕셔너리 (배열 대신 딕셔너리 사용: 메모리 절약하기 -> 숫자 범위가 매우 크기 때문!)

BFS 함수 정의

def bfs(v):
    q = deque([v])         # 시작 노드 큐에 넣기
    graph[v] = 0           # 시작 노드는 연산 횟수 0

    while q:
        node = q.popleft()  # 현재 노드 꺼내기

        if node == b:       # 목표 도달했으면 연산 횟수+1 반환
            return graph[node] + 1

다음 가능한 수들을 검사

        for next_node in (2*node, int(str(node)+'1')):
            if next_node <= b and next_node not in graph:
                graph[next_node] = graph[node] + 1
                q.append(next_node)