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

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

프로그래머스

 

해결 방법(실패)

이게 DFS 인지도 모르고 우선 코드를 짯는데, 11번만 시간초과가 발생했다. 인터넷에 검색해보니, DFS는 경우의 수가 많아질 때 검색량이 많아질 수도 있으니, BFS를 사용하라는 조언이 있었다.

 

%6 부분을 넣은것은 시간을 좀더 줄일 수 있을까 하여 시도해본건데, 시간을 많이 줄이지는 못했나보다. 이참에 BFS를 공부하는 좋은 기회이다. 

 

 

출처; https://dev.to/danimal92/difference-between-depth-first-search-and-breadth-first-search-6om

 

아래는 깊이우선탐색 DFS이다. 

#include <string>
#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;


void search(int x, int y, int n, string crr , int& min){
    
    if(x>y) return;
    if(min != -1 && crr.size() >= min) return;
    
    if(x==y)
    {
      if(min == -1 || crr.size() < min ) min = crr.size();
      return;
    }  
    
    char prev = crr.size() == 0 ? '-': crr[crr.size()-1];
    
    if(y%6 ==0) search(x,y/6, n, crr+"dD",min);
   
    if(prev != 'd' && y%3 == 0) search(x,y/3,n,crr+"D",min);
    if(prev != 'D' && y%2 == 0) search(x,y/2,n,crr+"d",min);
    
    search(x,y-n,n,crr+"m",min);
}

int solution(int x, int y, int n) {
    
    int min = -1;
    string crr = "";
    
    search(x,y,n,crr,min);
    return min;
}

 

 

해결 방법(성공)

아래는 BFS 이다. 

#include <string>
#include <vector>
#include <iostream>
#include <algorithm>
#include <queue>
#include <unordered_set>

using namespace std;

int solution(int x, int y, int n) {
    queue<pair<int, int>> q; // {현재 값, 연산 횟수}
    unordered_set<int> visited; // 방문 여부 저장
    q.push({y, 0});
    visited.insert(y);

    while (!q.empty()) {
        int curr = q.front().first;
        int steps = q.front().second;
        q.pop();

        if (curr == x) return steps;

        if (curr % 3 == 0 && visited.find(curr / 3) == visited.end()) {
            q.push({curr / 3, steps + 1});
            visited.insert(curr / 3);
        }
        if (curr % 2 == 0 && visited.find(curr / 2) == visited.end()) {
            q.push({curr / 2, steps + 1});
            visited.insert(curr / 2);
        }
        if (curr - n >= x && visited.find(curr - n) == visited.end()) {
            q.push({curr - n, steps + 1});
            visited.insert(curr - n);
        }
    }

    return -1;
}

 

 

마무리하며

x > y 로 가는것이 아니라, y> x로 나누면서 가는 방법을  택했다. 이 방법을 선택할 경우,  y에서 2로 나누어지지않는 경우, 3으로 나누어지지 않는 경우는 걸러낼 수 있기 때문이다.

 

탐색량이 많을 경우 BFS를 채택하도록 하자. . .