[PS] 백준 #9019 DSLR 문제풀이

...시간 복잡도 살려...자식노드 후보를 더 줄이고 빠르게 정답을 찾는 방법은 아직 찾지 못했습니다...뭔가 L, R에서 많이 줄일 수 있을 것 같습니다..

[ 문제풀이 ]

• Problem : 백준 #9019
• 구분 : BFS(너비 우선 탐색)
• 난이도 : Gold 5
• 풀이 방법 :
  • d, s, l, r 4개 연산의 경우의 수가 있고 이 연산을 거친 값 4개의 값이 현재값은 자식노드가 될 수 있습니다.
  • 최종값과 같아지는 최초의 자식까지의 height까지가 문제에서 요구하는 최소한의 명령어 나열이 됩니다.
  • 따라서, 해당 자식들과 해당 자식노드까지의 연산 나열을 queue에 넣어 돌리면서(중복 제외) 최종값에 도달할때까지 반복해줍니다.
  • 단, 해당 문제는 test case가 끝날때까지 d,s,l,r 연산을 하기 때문에 특정 숫자에 대한 d,s,l,r에 대한 결과값을 전역으로 선언한 배열에 저장해 연산을 중복으로 하지 않도록 하였고, 큐에 중복 자식노드가 들어가는 것을 막기 위해 방문배열을 이용해 큐에 넣기전에 체크해주었습니다.
    
    
  • 시간복잡도는 O(4^n) 정도인것 같아서, 사실 시간초과가 엄청 많이 났다가 갑자기 정답이 떠서 뭘로 시간복잡도를 줄여야할지 잘 모르겠습니다...아시는 분은 댓글 좀 남겨주세요...대체 왜 이게 골드 5 밖에 안되는거죠..

[ 🤟🏻 Code ] from ss-won

#include <iostream>
#include <algorithm>
#include <functional>
#include <vector>
#include <string>
#include <queue>
#define MAX 10000
using namespace std;
int t, s, e;
int memo[MAX][4];
bool visited[MAX];

void dslr(int curr){
    memo[curr][0] = curr * 2 % 10000;
    memo[curr][1] = (curr == 0) ? 9999 : curr - 1;
    memo[curr][2] = (curr * 10) % 10000 + (curr / 1000);
    memo[curr][3] = (curr / 10) + (curr % 10 * 1000);
}

void bfs(){
    queue<pair<int, string>> q;
    visited[s] = true;
    q.push({s, ""});
    while(!q.empty()){
        int curr;
        string depth;
        tie(curr, depth) = q.front(); q.pop();
        int d = memo[curr][0], s = memo[curr][1], l = memo[curr][2], r = memo[curr][3];
        if(d==0 && s==0 && l==0 && r==0){
            dslr(curr);
            d = memo[curr][0];
            s = memo[curr][1];
            l = memo[curr][2];
            r = memo[curr][3];
        }
        if(!visited[d]){
            if(d == e){
                cout << depth+'D' << "\n";
            }
            q.push({d,depth+'D'});
            visited[d] = true;
        }
        if(!visited[s]){
            if(s == e){
                cout << depth+'S' << "\n";
            }
            q.push({s,depth+'S'});
            visited[s] = true;
        }
        if(!visited[l]){
            if(l == e){
                cout << depth+'L' << "\n";
            }
            q.push({l,depth+'L'});
            visited[l] = true;
        }
        if(!visited[r]){
            if(r == e){
                cout << depth+'R' << "\n";
            }
            q.push({r,depth+'R'});
            visited[r] = true;
        }
    }
}

int main() {
    ios_base :: sync_with_stdio(false);
    cin.tie(NULL);
    cin >> t;
    while(t--){
        cin >> s >> e;
        fill(visited, visited+MAX, false);
        bfs();
    }
}