[프로그래머스] 숫자 변환하기 - Python

해당 문제는 bfs를 통해 문제를 해결하는 방식이다. bfs (Breadth-First Search)는 너비 우선 탐색으로 하나의 정점으로 부터 시작하여 차례대로 모든 정점들을 한 번씩 방문하는 것이다. 예를 들어, 특정 도시에서 다른 도시로 갈 수 있는지 없는지 판단할 때 사용할 수 있다. 

 

시작 정점으로부터 가장 가까운 정점에 먼저 방문하고, 멀리 떨어져 있는 정점을 나중에 방문하는 방식으로, 두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 이를 사용한다. 해당 문제는 두 노드 즉, x, y 간의 최단 경로를 찾는 문제로 해석할 수 있다. 

def solution(x, y, n):
    answer = 0
    s = set()
    s.add(x)
    
    while s:
        if y in s:
            return answer
        nx = set()
        
        for i in s:
            if i+n <= y:
                nx.add(i+n)
            
            if i*2 <= y:
                nx.add(i*2)
            
            if i*3 <= y:
                nx.add(i*3)
        
        s = nx
        answer += 1 
    
    return -1

본 문제에서는 n, *2, *3의 연산이 가능하다고 했다. 그렇기 때문에 while 문에서 각 연산이 y 즉, 도달하고자 하는 값보다 작거나 같으면 다음 집합에 더해준다. 이 과정을 계속 반복하고, i+n, i*2, i*3이 y보다 커진다면 while 문을 빠져나오게 된다. 그렇다면 -1를 return 하게 된다. 만약에 해당 값이 y와 같아지면 if y in s: 조건에서 answer 즉, 몇 번 연산을 진행했는지 값이 반환된다.