BOJ 16953. [Silver2] A -> B

[hojongs]

Problem link

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

Problem abstraction

문제의 핵심을 요약한다. 체계적인 문제 접근을 위해, 문제를 추상화한다

적합한 자료구조를 생각한다

Design(Plan) algorithm

# 1

---
# 2

---
# 3

Algorithm idea

추상화한 문제 이해를 기반으로 알고리즘의 대략적인 구현 계획을 서술한다

Pseudo-code

idea를 수도 코드로 작성해본다

Validate algorithm

알고리즘의 유효 여부를 구현 전에 검증한다

예제 입력을 수도 코드로 계산해보고, 놓친 알고리즘 오류가 있는지 확인한다

Impl

import sys
from collections import deque

readl = sys.stdin.readline


def f():
    """
    BFS
    """
    a, b = map(int, readl().split())
    q = deque([(a, 0)])
    result = -1
    while q:
        v, cnt = q.popleft()
        if v == b:
            result = cnt + 1
            break
        elif v < b:
            q.append([v * 2, cnt + 1])
            q.append([v * 10 + 1, cnt + 1])
    print(result)


f()

Self-feedback

구조적 접근: 문제를 추상화하여 구조적으로 접근했는가?

사고력: 알고리즘을 완전히 이해했는가? (충분한 사고력을 가졌는가?)

구현력: 알고리즘을 신속, 정확하게 구현했는가?

실수로 DFS로 구현함 (popleft -> pop)
그래서 PQ로 구현을 잘못 변경하다가, 알고리즘을 글로 쓰는 과정에서 BFS로 다시 돌아감