[c++] BOJ 9019 :: DSLR

난이도 : 골드 5

걸린 시간 : 1시간 30분

 

문제

DSLR 문제 바로가기

 

풀이

• DSLR이라는 4가지 경로가 있다고 생각하고 bfs

 

코드

#include <iostream>
#include <queue>
#include <string>

using namespace std;

struct point
{
    int prev;
    char state;
    int visited = -1;
};

char dslrArr[4] = { 'D', 'S', 'L', 'R' };

int dslrResult(int type, int num) {
    int tmp;
    switch (type) {
    case 0 :
        return (num* 2) % 10000;
    case 1 :
        if (num == 0)
            return 9999;
        else
            return num - 1;
    case 2 :
        tmp = num / 1000; // pow 사용 x => 시간초과
        return (num - tmp * 1000) * 10 + tmp;
    case 3 :
        return (num % 10) * 1000 + num / 10;
    }
}

void getAnswer(vector<char>& ans, point* memo, int a, int b) { // string을 붙이는 식으로 => 시간초과
    int idx = b;
    while (1){
        if (idx == a) break;
        ans.push_back(memo[idx].state);
        idx = memo[idx].prev;
    }
}

int main() {
    int T; cin >> T;
    while (T--) {
        int A; int B;
        cin >> A >> B;

        int flag = 0;
        vector<char> answer;
        point memo[10001];
        queue<int> que; 

        que.push(A); // 초기화 수 넣기
        memo[A].visited = 1;
        while (!que.empty()) {
            int tmp = que.front(); que.pop();
            for (int i = 0; i < 4; i++) {
                if (tmp == 0 && i != 1) // 0에 곱셈 연산 의미 x => 시간 개선
                    continue;

                int res = dslrResult(i, tmp);
                if (memo[res].visited != -1) { // 이미 들른 곳
                    continue;
                }

                memo[res].prev = tmp;
                memo[res].state = dslrArr[i];
                memo[res].visited = 1;

                if (res == B) {
                    // B가 나옴
                    getAnswer(answer, memo, A, B);
                    flag = 1;
                    break;
                } else {
                    que.push(res);
                }
            }
            if (flag)
                break;
        }
        for (int i=answer.size()-1; i >= 0; i--) {
            cout << answer[i];
        }
        cout << '\n';
    }
}

 

주의할 점

• pow 연산은 생각보다 느리다 => 상수로 사용할 수 있다면 상수로 사용하자.
• string 이어붙이기 연산은 생각보다 느리다 => vector를 이용하여 저장하고 접근하는 것이 더 빠르다.
  • 다른 코드들 보니까 string 이어붙이기 연산은 괜찮은 듯하다.
• 테스트케이스가 있는 문제는 초기화에 신경쓰자.

 

결과

아이디	메모리	시간	언어	코드 길이
gmldms784	2024	1512	C++17 / 수정	1843