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

---

🔗 문제 링크

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

프로그래머스

---

728x90

👩‍💻 코드

#include <queue>
#include <vector>
#include <unordered_set>

using namespace std;

int solution(int x, int y, int n) {
    if (x == y) {
        return 0;
    }

    queue<pair<int, int>> q;
    unordered_set<int> visited;
    
    q.push({x, 0});
    visited.insert(x);
    
    while (!q.empty()) {
        int current = q.front().first;
        int count = q.front().second;
        q.pop();
        
        int next_values[3] = {current + n, current * 2, current * 3};
        
        for (int i = 0; i < 3; i++) {
            int next = next_values[i];
            
            if (next == y) {
                return count + 1;
            }
            
            if (next <= y && visited.find(next) == visited.end()) {
                q.push({next, count + 1});
                visited.insert(next);
            }
        }
    }
    
    return -1;
}

---

📝 풀이

BFS 알고리즘을 사용하여 문제를 해결했습니다.

 

q에는 { 현재숫자, 연산 횟수 } 형태로 저장합니다.

visited에는 방문한 숫자를 저장합니다.

 

q가 비어있지 않는 동안 반복문을 실행합니다.

q에서 숫자를 꺼내어 각 연산들을 실행합니다.

연산을 실행한 값이 y와 같다면 count+1을 return 합니다.

연산을 실행한 값이 y와 같지 않지 않지만 y이하고 방문한 적 없는 숫자라면 q와 visited에 저장합니다.

 

반복문이 종료된 후에도 x가 y에 도달하지 못 했다면 -1을 return 합니다.