DSLR

 

BFS 문제, 사실 처음봤을때 스페셜저지에 이것저것 고려해보니 괴랄한문제라고 생각이많이들었던건데

마음을 조금진정시키고 차분히 읽어보자.

 

일단 전체적인 숫자의 길이 수가 4개뿐이며, 그 숫자의 크기가 10000을 넘을수없다.

 

D일때 2씩 곱해나가면서 만이 넘어갈경우, 나머지를 지정하고

S는 1씩 감소,

L은 왼쪽방향으로 숫자이동

R은 오른쪽방향으로 숫자이동

 

이 각각의 경우의 수들이 전부 가치가 1씩 이라는점이다.->BFS로 풀수있다.

하지만, 문제를보면 최소 경로의 지나온 횟수를 물어보는 문제가아니다.

횟수가 아닌, 목표지점까지 오게된 경로를 구하는것이다,.

어떻게보면 숨바꼭질4와 비슷하다 생각이됬고 그에 따라 최소경로 구한뒤 -> 트랙킹을했다.

 

#include<cstdio>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<queue>

using namespace std;

int a[4];
bool d[10000];
int c[10000];
int n,goal;
void module(int x){
    a[0] = x / 1000;
    a[1] = (x - a[0]*1000)/100;
    a[2] = (x - a[0]*1000 - a[1]*100)/10;
    a[3] = x - a[0]*1000 - a[1]*100-a[2]*10;
}
int demodule(int x){
    x = ((a[0]*10+a[1])*10+a[2])*10+a[3];
    return x;
}

int L(int x){
    module(x);
    int temp = a[0];
    for(int i = 0; i < 3; i++){
        a[i] = a[i+1];
    }
    a[3] = temp;
    return demodule(x);
}
int R(int x){
    module(x);
    int temp = a[3];
    for(int i = 3; i >= 1 ; i--){
        a[i] = a[i-1];
    }
    a[0] = temp;
    return demodule(x);
}

void bfs(){
    queue<int> q;
    q.push(n);
    d[n] = true;
    while(!q.empty()){
        int x = q.front();
        int l = L(x); int r = R(x);
        q.pop();
        if(x == goal){
            return;
        }
        if(d[(x*2) % 10000] == false){
            q.push(((x*2) % 10000));
            d[(x*2)% 10000] = true;
            c[(x*2)%10000] = 1;
        }
        if(x - 1 < 0){
            if(d[9999] == false){
                q.push(9999);
                d[9999] = true;
                c[9999] = 2;
            }
        }
        if(x - 1 >= 0){
            if(d[x-1] == false){
                q.push(x-1);
                d[x-1] = true;
                c[x-1] = 2;
            }
        }
        if(d[l]== false){
            q.push(l);
            d[l] = true;
            c[l] = 3;
        }
        if(d[r] == false){
            q.push(r);
            d[r] = true;
            c[r] = 4;
        }
    }
}
vector<char> visit;
void tracking(){
    int x = goal;
    visit.clear();
    while(true){
        if(x == n){
            break;
        }
        if(c[x] == 1){
            if(d[(x + 10000)/2] == true){
                x = (x + 10000)/2;
                visit.push_back('D');
            }
            else if(d[x/2] == true){
                    x = x/2;
                    visit.push_back('D');
            }
        }
        if(c[x] == 2){
            if(x == 0){
                x = 9999;
                visit.push_back('S');
            }
            else{
                x -=1;
                visit.push_back('S');
            }
        }
        if(c[x] == 3){
            x = R(x);
            visit.push_back('L');
        }
        if(c[x] == 4){
            x = L(x);
            visit.push_back('R');
        }

    }
}

int main(){
    int tc;
    cin>>tc;
    for(int t =0; t<tc; t++) {
        cin >> n >> goal;
        bfs();

        tracking();
        for(int i = 0; i < visit.size(); i++){
            cout<<visit[i];
        }
        cout<<'\n';
        memset(d,false,sizeof(d));
        memset(c,0,sizeof(c));
    }
}

 

위와 같이 트랙킹을해서 char 벡터에, 지나온 경로를 담고 나중에 출력하는방식이였지만, 전체적으로 BFS하는횟수도 많거니와

그에따라 트랙킹의 갯수도 늘어나면 늘어날수록 시간복잡도가 기하급수적으로 증가하기때문에, 시간초과가 나버렸다.

 

이때 내가할수있는 방식변경법은, 경로를 구하고 -> 다시 돌아가면서 체킹한다 가 아닌,

" 경로를 구하면서, 갔던방법을 체킹한다 "이다.

 

경로를 가면서 체킹하는 방법으로 생각난게,

어차피 출력이 문자열 이기떄문에, string 배열을 만들어서 최초경로에서부터 하나하나 담아가는것을생각했다.

#include<cstdio>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<queue>

using namespace std;

int a[4];
bool d[10000];
string ans[10000];


int L(int x){
    a[0] = x / 1000;
    a[1] = (x - a[0]*1000)/100;
    a[2] = (x - a[0]*1000 - a[1]*100)/10;
    a[3] = x - a[0]*1000 - a[1]*100-a[2]*10;
    int temp = a[0];
    for(int i = 0; i < 3; i++){
        a[i] = a[i+1];
    }
    a[3] = temp;
    x = a[0]*1000 + a[1]*100 + a[2] *10 +a[3];
    return x;
}
int R(int x){
    a[0] = x / 1000;
    a[1] = (x - a[0]*1000)/100;
    a[2] = (x - a[0]*1000 - a[1]*100)/10;
    a[3] = x - a[0]*1000 - a[1]*100-a[2]*10;
    int temp = a[3];
    for(int i = 3; i >= 1 ; i--){
        a[i] = a[i-1];
    }
    a[0] = temp;
    x = a[0]*1000 + a[1]*100 + a[2] *10 +a[3];
    return x;
}

void bfs(int n, int goal){
    queue<int> q;
    q.push(n);
    d[n] = true;
    ans[n] = "";
    while(!q.empty()){
        int x = q.front();
        int l = L(x); int r = R(x);
        q.pop();
        if(x == goal){
            return;
        }
        if(d[(x*2) % 10000] == false){
            q.push(((x*2) % 10000));
            d[(x*2)% 10000] = true;
            ans[(x*2)%10000] = ans[x] + "D";
        }

        if(x - 1 >= 0){
            if(d[x-1] == false){
                q.push(x-1);
                d[x-1] = true;
                ans[x-1] = ans[x] + "S";
            }
        }
        if(x -1 < 0) {
            if(d[9999] == false){
                q.push(9999);
                d[9999] = true;
                ans[9999] = ans[x]+ "S";
            }
        }
        if(d[l]== false){
            q.push(l);
            d[l] = true;
            ans[l] = ans[x] +"L";
        }
        if(d[r] == false){
            q.push(r);
            d[r] = true;
            ans[r] =ans[x]+"R";
        }
    }
}

int main(){
    int tc;
    cin>>tc;
    for(int t =0; t<tc; t++) {
        int n,goal;
        cin >> n >> goal;
        bfs(n,goal);

        cout<<ans[goal];
        cout<<'\n';
        memset(d,false,sizeof(d));
    }
}

 

이런식으로, 이전경로에서 하나하나씩 문자열을담아가면, BFS자체에 시간복잡도내에서 충분히 최종목표치까지의

시간복잡도로 합쳐져서 괜찮은방법이라고 생각했다.

그리고 memset 을 방문경로에 대해서만 썼는데, 어차피 BFS내 조건에서 최초 시작점만 초기화해주면, 다른곳에 들어갈때 최초경로 + 지금경로로 입력되기떄문에, 시간복잡도를 한층 더줄이는 방법이라고 생각했다.

 

-구현하기 까다로웠던 문제-