[백준] 9019.cpp : DSLR

www.acmicpc.net/problem/9019

9019번: DSLR

#include <iostream>
#include <queue>
#define pairs pair<int,string>          // 큐에 넣어줄 데이터 형식, <값, 명령어>
using namespace std;

int tc = 0;
int a, b;
char funcs[4] = {'D', 'S', 'L', 'R'};
int answers[10000][4];                  // 각 숫자별로 DSLR 연산 시 나올 결과값 선계산
bool visited[10000];

int ret(int temp, int func)             // DSLR 각 연산
{
    if(func == 0)       temp = (temp * 2) % 10000;                  // D
    else if(func == 1)  temp -= 1;                                  // S
    else if(func == 2)  temp = (temp % 1000) * 10 + (temp / 1000);  // L
    else                temp = (temp / 10) + (temp % 10) * 1000;    // R

    if(temp < 0) temp = 9999;
    return temp;
}

int main(void)
{
    cin >> tc;
    for(int i = 0 ; i < 10000 ; i++)            // 숫자별 DSLR 값들 선계산
    {
        for(int j = 0 ; j < 4 ; j++)
        {
            answers[i][j] = ret(i, j);
        }
    }
    while(tc--)
    {
        for(int i = 0 ; i < 10000 ; i++) visited[i] = false;    // 케이스마다 방문 정보 초기화
        cin >> a >> b;

        queue<pairs> q;
        int cur;
        q.push(pairs(a, ""));                   // 첫 숫자 입력
        visited[a] = true;                      // 첫 숫자 방문 처리
        while(true)
        {
            cur = q.front().first;
            if(cur == b) break;                 // 만약 목표 값에 도달했다면 종료
            for(int i = 0, k ; i < 4 ; i++)     // 그게 아닐 경우 DSLR 해당하는 값들 큐에 푸시
            {
                k = answers[cur][i];
                if(visited[k]) continue;        // 만약 해당 명령어의 값이 이미 처리되었던 값이면 스킵
                visited[k] = true;              // 아닐 경우 방문 처리 해주고
                q.push(pairs(k, q.front().second + funcs[i]));  // 해당 명령어의 값을 푸시해줌
            }
            q.pop();
        }
        cout << q.front().second << '\n';       // 목표 값까지 도달한 명령어 출력
    }
}

 

[Approach]

1. 입력받은 시작값에서 (값 , 명령어) 의 형식으로 각각 DSLR 을 다 넣어서 목표하는 값의 명령어 구하기 (BFS)

     -> 메모리 초과 -> 연산 편하게 하려고 값을 숫자가 아닌 string 으로 넣은게 문제인듯

2. 숫자로 바꿔서 저장하기 (L, R 도 나머지 연산으로 구하면 되는 걸 굳이 문자열로 했네..)

3. 방문 여부 체크 배열을 전역변수로 설정해놓고 테케마다 초기화시켜주지 않아서 런타임 에러 발생.

     그래도 시간초과가 뜬다.

4. 각 숫자별로 DSLR 수행 시 나오는 값들을 처음에 싹 다 구해놓기

5. BFS 에서 팝 할때 방문 검사와 반복 종료를 하지 말고 푸시할 때 미리미리 처리해주기. 푸시해줄 때는 방문하지 않았다는 처리가 되

     어 있어서 그냥 냅다 넣어버리니까 시간초과가 계속 났던 것 같다.

 

[Point]

1. BFS 처리 시 주의할 점들(방문 처리, 초기화 등)

 

[More]

1. 명령어를 따로 저장하지 않고 경로를 추적하는 거 같다. 비트값을 조정해서? (17368810)

2. 큐를 사용하지 않고 배열로만 접근 (12600860)