[BOJ] 9019 DSLR

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

9019번: DSLR

---------------------------------------------------핵심 알고리즘--------------------------------------------

 

bfs

 

---------------------------------------------------풀이----------------------------------------------------

 

pair<현재의 A값, 현재까지 진행한 명령어>를 큐에 담아 bfs 탐색을 진행한다.

이 때, 메모리 초과를 방지하기 위해 이미 방문한 A의 값들을 visited[10000]에서 true로 만들며 다시 방문하지 않도록 했다.

즉, visited[현재의 A값] = true로 만드는 것이다.

레지스터에 들어갈 수 있는 값이 네 자리 숫자로 정의되어 있기 때문에 가능한 방식이었다.

 

현재 바뀐 A값을 네 가지 명령어를 각각 실행해, 아직 방문한 적이 없는 값이라면 큐에 삽입하며 B가 될 때까지 진행한다.

맨 처음 B를 만들었을 때가 가장 적게 명령어를 사용한 것이므로 그 때의 명령어 string을 출력한다.

#define FASTIO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <queue>
#include <cmath>
#include <stack>
#include <limits.h>
#include <deque>

using namespace std;

int A, B;

int exec_D(int n){
    return (n*2)%10000;
}

int exec_S(int n){
    n--;
    if(n < 0){
        n = 9999;
    }
    return n;
}

int exec_L(int n){
    n *= 10;
    return (n+(n/10000))%10000;
}

int exec_R(int n){
    return (n/10) + (n%10)*1000;
}

bool visited[10000] = {false, };

string solution(){
    // visited 초기화
    for(int i = 0; i < 10000; i++){
        visited[i] = false;
    }
    pair<int, string> cur;
    cur.first = A; cur.second = "";
    // 현재의 A값, 명령어 모음
    queue<pair<int, string> > q;
    q.push(cur);
    visited[cur.first] = true;
    while(!q.empty()){
        cur = q.front();
        q.pop();

        // B로 변경에 성공한 경우
        if(cur.first == B){
            return cur.second;
        }

        // 네 명령어 사용해 큐에 삽입
        int n = exec_D(cur.first);
        if(!visited[n]) {
            q.push(make_pair(n, cur.second + "D"));
            visited[n] = true;
        }
        n = exec_S(cur.first);
        if(!visited[n]){
            q.push(make_pair(n, cur.second + "S"));
            visited[n] = true;
        }
        n = exec_L(cur.first);
        if(!visited[n]){
            q.push(make_pair(n, cur.second + "L"));
            visited[n] = true;
        }
        n = exec_R(cur.first);
        if(!visited[n]){
            q.push(make_pair(n, cur.second + "R"));
            visited[n] = true;
        }
    }
    return "";
}

int main(void){
    FASTIO;
    int T;
    cin >> T;
    for(int t = 0; t < T; t++){
        cin >> A >> B;
        cout << solution() << "\n";
    }
    return 0;
}

 

---------------------------------------------------후기----------------------------------------------------

 

bfs를 시도하면서, 현재의 A값을 저장하고 그 때의 명령어 모음을 담기 위해 pair<int,string>을 큐에 담아 사용했는데,

1~3%에서 메모리 초과가 발생했다.

그래서 visited[10000]를 선언해 특정 숫자를 한 번만 방문하도록 했다.

그런데 이제 3%에서 틀렸다고 뜨는 문제가 있었다.

문제 이해를 살짝 잘못해서 벌어진 일이었다....

2. S: S 는 n에서 1 을 뺀 결과 n-1을 레지스터에 저장한다. n이 0 이라면 9999 가 대신 레지스터에 저장된다

문제에서 이 부분을 구현하기 위해 n--; 한 뒤 n이 0이면 9999이도록 구현했는데,

다시 살펴보니 n이 0이면 n-1을 한 값이 9999가 되도록 구현해야 하는 문제였다ㅠㅠ(사실 이게 더 자연스러운데 왜..)

이 문제를 고치니 무사히 통과할 수 있었다.

 

이 문제에서의 또 한가지 문제는 pair<>로 int와 string을 저장하면서 string에 계속 append 하는 방식으로 이전 값을 저장한다는 것이다.

백트래킹을 사용해 이전 값에서 찾아오는 방식도 찾으면 올려야겠다 :0