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

문제 링크

숫자 변환하기

풀이

BFS를 이용하는 문제

1. x와 y가 같다면 return 0 -> 이 처리를 안해줘서 하나 틀렸었음
   1-1. queue에 {x,0} 값을 push, x는 현재 값, 0은 연산 횟수. visited[x]=1도 해준다.
2. q가 빌 때까지 반복한다.
   2-1. 차례대로 num+n, num*2, num*3을 계산해서 계산 값이 y를 넘거나, 이미 방문했다면(방문했다면 그 연산횟수가 최소일테니) continue, calc[i]==y라면 숫자를 찾은거니 return cnt+1
3. q에 현재 값 push, 방문처리해준다.
4. 해당 반복문이 끝나도 return 처리가 안되는거면 y를 못찾은 채 y를 넘어버린 것이므로 (못찾은 것이므로) return -1

코드

#include <string>
#include <vector>
#include <queue>

using namespace std;

int BFS(int x, int y, int n)
{
    queue<pair<int,int>> q;
    vector<int> visited(y+1);
    
    if(x==y) return 0; // 이미 x와 y가 같다면
    
    q.push({x,0});
    visited[x] = 1;
    
    while(!q.empty())
    {
        int num = q.front().first;
        int cnt = q.front().second;
        q.pop();
        
        int calc[3] = {num+n, num*2, num*3};
        for(int i=0;i<3;i++)
        {
            if(calc[i]>y) continue; // 계산 값이 y를 넘으면
            if(visited[calc[i]]==1) continue; // 이미 방문했던 숫자라면
            if(calc[i]==y) return cnt+1; // 찾으면 return
            
            q.push({calc[i],cnt+1});
            visited[calc[i]] = 1;
        }
    }
    
    return -1;
}

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