S2 16953. A → B

문제 보기 :  16953번: A → B

---

문제

• 정답률 : 39%

---

작성 코드

# 입력값을 받음 (시작 값 n, 목표 값 m)
n, m = map(int, input().split())

answer = -1  # 결과 초기화
visited = set()  # 방문한 노드를 기록할 집합
visited.add(n)  # 시작 노드를 방문 처리

from collections import deque
dd = deque([(n, 1)])  # BFS를 위한 큐 (현재 값, 연산 횟수)

while dd:
    now, cal = dd.popleft()  # 큐에서 현재 값과 연산 횟수를 꺼냄
    
    if now == m:  # 목표 값에 도달한 경우
        answer = cal  # 결과에 연산 횟수 저장
        break

    # 다음 가능한 상태 계산
    can = (now * 2, (now * 10) + 1)
    for c in can:
        if 0 <= c <= m and c not in visited:  # 범위 내 값이며 방문하지 않은 경우
            visited.add(c)  # 방문 처리
            dd.append((c, cal + 1))  # 다음 상태를 큐에 추가

# 결과 출력 (목표에 도달하지 못하면 -1)
print(answer)

---

풀이

1. 시작 값 n과 목표 값 m을 입력받아 BFS 탐색을 통해 최소 연산 횟수를 계산한다.

2. BFS를 위한 큐를 초기화하고, 방문한 노드는 set을 이용해 기록하여 중복 계산을 방지한다.

3. 큐에서 현재 값과 연산 횟수를 꺼내, 목표 값 m에 도달하면 연산 횟수를 결과로 저장하고 종료한다.

4. 현재 값에서 가능한 다음 상태 (값 * 2)와 (값 * 10 + 1)을 계산하고, 범위 내에서 아직 방문하지 않은 경우만 큐에 추가한다.

5. BFS가 종료되면 결과를 출력하며, 목표 값에 도달하지 못한 경우 1을 출력한다.