[프로그래머스 숫자 변환하기] c++ (풀이,코드,bfs)

문제 링크

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

프로그래머스

 

문제

 

 

풀이 및 코드

굉장히 간단한 bfs문제로 최소 횟수를 구하는 문제였습니다.

 

근데 잠시 틀인 풀이 코드(효율성x)를 보고 가시죠.

 

틀린 코드

#include <string>

#include <vector>

#include <queue>

using namespace std;

int solution(int x, int y, int n) {

    int answer = 0;

    queue<pair<int,int>> q; //숫지,횟수

    q.push({x,0});

   

    while(!q.empty()){

        int num = q.front().first;

        int cnt = q.front().second;

        q.pop();

       

        if(num == y){

            return cnt;

        }

       

        if(num + n <= y)

            q.push({num + n,cnt + 1});

        if(num *2 <= y)

            q.push({num *2,cnt + 1});

        if(num * 3 <= y)

            q.push({num * 3,cnt+1});

    }

    return -1;

}

왜 이런 결과가 나왔을까요? 

 

너비 탐색을 하면서 간단하게 하는건데 정말 레벨2를 만만하게 본건가? 

 

혹시 위의 코드를 보시고 무언가 잘못된게 있다는것을 찾아볼 수 있나요?

 

아래의 코드를 보기 전에 한번 생각해보시면 좋을것 같네요 :)

 

고친 코드

#include <vector>

#include <queue>

using namespace std;

int solution(int x, int y, int n) {

    int answer = 0;

    queue<pair<int,int>> q; //숫지,횟수

    bool visited[1000001] = {false,};

    q.push({x,0});

   

    while(!q.empty()){

        int num = q.front().first;

        int cnt = q.front().second;

        q.pop();

       

        if(num == y){

            return cnt;

        }

       

        if(num + n <= y && !visited[num + n]){

            q.push({num + n,cnt + 1});

            visited[num + n] = true;

        }

        if(num *2 <= y&& !visited[num * 2]){

            q.push({num *2,cnt + 1});

            visited[num * 2] = true;

        }

        if(num * 3 <= y && !visited[num * 3]){

            q.push({num * 3,cnt+1});

            visited[num * 3] = true;

        }

    }

    return -1;

}

덤벙 덤벙 거리는 성격이라 방문여부를 확인하고 조건문에서 제외 시키는 것에 대한 체크 과정을 빼먹어 버렸습니다..

 

시간복잡도

 

위 그림은 2번의 과정만 진행을 하였는데 만약 bfs의 visited(방문여부 체크)가 없게 된다면 어떻게 될까요?

 

그것은 숫자의 차이가 어마무시하다면 3^n이됩니다.

 

헤헿.. 또 덤벙거렸다.