[백준][C++] 9019-DSLR

📌문제 설명

https://www.acmicpc.net/problem/9019

 

💡생각

처음에 아무리 생각해도 해결방안이 생각나지 않아서 다른 분의 블로그를 읽는데 BFS라는 글자를 보고 번뜩 하면서 해결책이 생각났다!!!!!

 

• 모든 경우의수를 다 구해야 하는건가?? -> 처음에 트리를 그려보면서 백트래킹으로 풀이를 해야할지에 대한 고민도 했었지만 너무 많은 수의 계산이 필요할 거 같아서 하지 않았다.
• 그럼 어떻게 해야하지?? -> BFS??
• 처음했던 생각을 백트래킹 말고 BFS를 이용해서 해야겠다고 판단했으면 참고를 하지 않아도 풀었을텐데 좀 아쉽다!!!

문제 풀이

• 처음 입력받는 수를 Queue에 저장한다.
• Queue는 어떤 계산을 통해 도달하게 되었는지 알아야 하기 때문에 pair를 통해 이전에 사용했던 계산을 저장하면서 Push해준다.
• 만약 방문하지 않았다면 해당 값, 이전에 수행했던 연산 + 이번에 값을 만들기 위해 수행했던 연산을 더해줘서 pair형태로 저장한다.
• 4개의 연산을 모두 수행하면 visited를 통해 이전에 방문했는지 계산하고 방문했었다면 Pass 아니면 연산 후 Push해준다.
• 원하는 값을 찾는다면 반복문을 종료하고 출력한다.

🔥풀이

#include <iostream>
#include <queue>
using namespace std;

int shiftRight(const int num){
    int right_num = (num % 10) * 1000;
    int left_num = (num/10);
    return right_num + left_num;
}
int shiftLeft(const int num){
    int right_num = (num/1000);
    int left_num = (num%1000) * 10;
    return left_num + right_num;
}
int minusOne(const int num){
    int temp = num - 1;
    if(temp == -1){
        return 9999;
    }
    return temp;
}
int multiple(const int num){
    return (num*2) % 10000;
}
int main()
{
    int T;
    cin >> T;
    int start, distance;

    for(int i = 0; i < T; i++){
        cin >> start >> distance;
        bool visited[10001] = {false,};
        queue<pair<int,string> > q;
        q.push(make_pair(start, ""));
        visited[start] = true;
        while(!q.empty()){
            int fir = q.front().first;
            string sec = q.front().second;
            q.pop();
            if(fir == distance){
                cout << sec << "\n";
                break;
            }
            int firD = multiple(fir);
            int firS = minusOne(fir);
            int firL = shiftLeft(fir);
            int firR = shiftRight(fir);
            if(!visited[firD]){
                q.push(make_pair(firD, sec+"D"));
                visited[firD] = true;
            }
            if(!visited[firS]){
                q.push(make_pair(firS, sec+"S"));
                visited[firS] = true;
            }
            if(!visited[firL]){
                q.push(make_pair(firL, sec+"L"));
                visited[firL] = true;
            }
            if(!visited[firR]){
                q.push(make_pair(firR, sec+"R"));
                visited[firR] = true;
            }
        }
    }
}

참고

https://jangkunstory.tistory.com/126

[백준 / C++] 9019번: DSLR