[프로그래머스 Lv. 2] 숫자 변환하기

DaeHoon·2023년 1월 27일
0

프로그래머스

목록 보기
13/16

문제

https://school.programmers.co.kr/learn/courses/30/lessons/154538

접근

1) 최소 연산 횟수를 저장하는 리스트를 0으로 초기화한다.
2) x에서 y로 가는 최단 거리를 bfs로 구한다.
3) 이 때 x에서 n을 더하는 경우, 2를 곱하는 경우, 3을 곱하는 경우에 대해 분기를 쳐서 큐에 넣어준다

Code

from collections import deque


def solution(x, y, n):
    def bfs(x, y, n):
        q = deque()
        dist[x] = 1
        q.append(x)

        while q:
            x = q.popleft()
            if 0 <= x + n <= 1000000 and dist[x + n] == 0:
                dist[x + n] = dist[x] + 1
                q.append(x + n)
            if 0 <= x * 2 <= 1000000 and dist[x * 2] == 0:
                dist[x * 2] = dist[x] + 1
                q.append(x * 2)
            if 0 <= x * 3 <= 1000000 and dist[x * 3] == 0:
                dist[x * 3] = dist[x] + 1
                q.append(x * 3)

    dist = [0] * 1000001
    bfs(x,y,n)

    return dist[y]-1

여담

백준의 숨바꼭질과 매우 유사한 문제
https://www.acmicpc.net/problem/1697

profile
평범한 백엔드 개발자

0개의 댓글