[프로그래머스] Level2 숫자 변환하기(python)

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

프로그래머스

 

1. 문제 해결 방법

BFS를 이용해 x+n, x*2, x*3 만큼 이동시키며 문제를 풀었다.

 

백준 숨바꼭질과 유사한 문제라서 한 번 풀어보시길 추천

 

from collections import deque

def solution(x, y, n):
    visit = [0] * (y+1)
    visit[x] = 1
    
    if bfs(x,y,n,visit) == False:
        return -1
    else:
        return visit[y]-1
    
    
def bfs(x,y,n,visit):
    queue = deque()
    queue.append(x)
    
    while queue:
        x = queue.popleft()
        
        if x == y:
            return visit[y]
    
        for i in (x+n, x*2, x*3):
            if i > y:
                continue
            if visit[i] == 0:
                visit[i] = visit[x] + 1
                queue.append(i)

 

 

2. 다른 풀이

def solution(x, y, n):
    answer = 0
    s = set()
    s.add(x)

    while s:
        if y in s:
            return answer

        nxt = set()
        for i in s:
            if i+n <= y:
                nxt.add(i+n)
            if i*2 <= y:
                nxt.add(i*2)
            if i*3 <= y:
                nxt.add(i*3)
        s = nxt
        answer+=1

    return -1

 

set함수는 생각해본적이 한 번도 없는데 이런 풀이도 있었네

 

사람들은 대단해