[BaekJoon] #9019 - DSLR [Java][C++]

문제 링크

---

1. 아이디어

주어진 D, S, L, R 연산을 활용해서 $A$를 $B$로 바꾸는 최소 명령어 나열을 구하는 문제로 BFS와 역추적을 활용하면 해결할 수 있다.

먼저 주어진 명령어를 처리할 수 있어야 하는데 임의의 수 $n$에 대해 아래와 같이 각 명령어가 적용된 결과를 구할 수 있다.

• D: $(n \times 2) \bmod 10{,}000$
• S: $(n - 1 + 10{,}000) \bmod 10{,}000$
• L: $(n \bmod 1{,}000) \times 10 + n / 1{,}000$
• R: $(n \bmod 10) \times 1{,}000 + n / 10$

역추적의 경우 현재 수가 어떤 수에서 왔는지를 기록하는 prv 배열과 해당 수로 올 때 어떤 연산이 적용됐는지 기록하는 type 배열을 활용해서 변환을 통해 $B$가 됐을 때, prv 배열을 통해 역추적하며 연산들을 구해내면 된다.

---

2. 복잡도

접근	시간	공간
풀이	$O(T)$	$O(1)$

($T$ = 테스트 케이스 수)

---

3. 코드

풀이 [Java][C++]

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st;

        int t = Integer.parseInt(br.readLine());
        while (t-- > 0) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());

            sb.append(bfs(a, b)).append("\n");
        }

        System.out.print(sb);
    }

    static String bfs(int a, int b) {
        Queue<Integer> q = new ArrayDeque<>();
        q.offer(a);

        boolean[] vis = new boolean[10000];
        vis[a] = true;

        int[] prv = new int[10000];
        Arrays.fill(prv, -1);
        char[] type = new char[10000];

        while (!q.isEmpty()) {
            int cur = q.poll();
            if (cur == b) {
                StringBuilder sb = new StringBuilder();

                while (prv[cur] != -1) {
                    sb.append(type[cur]);
                    cur = prv[cur];
                }

                return sb.reverse().toString();
            }

            int d1 = cur * 2 % 10000;
            if (!vis[d1]) {
                q.offer(d1);
                vis[d1] = true;
                prv[d1] = cur;
                type[d1] = 'D';
            }

            int d2 = (cur - 1 + 10000) % 10000;
            if (!vis[d2]) {
                q.offer(d2);
                vis[d2] = true;
                prv[d2] = cur;
                type[d2] = 'S';
            }

            int d3 = cur % 1000 * 10 + cur / 1000;
            if (!vis[d3]) {
                q.offer(d3);
                vis[d3] = true;
                prv[d3] = cur;
                type[d3] = 'L';
            }

            int d4 = cur % 10 * 1000 + cur / 10;
            if (!vis[d4]) {
                q.offer(d4);
                vis[d4] = true;
                prv[d4] = cur;
                type[d4] = 'R';
            }
        }

        return null;
    }
}

#include <bits/stdc++.h>
using namespace std;

bool vis[10000];
int prv[10000];
char type[10000];
string ans;

void bfs(int a, int b) {
    queue<int> q;
    q.push(a);

    vis[a] = true;

    while (!q.empty()) {
        int cur = q.front();
        q.pop();

        if (cur == b) {
            while (prv[cur] != -1) {
                ans += type[cur];
                cur = prv[cur];
            }

            reverse(ans.begin(), ans.end());
            return;
        }

        int d1 = cur * 2 % 10000;
        if (!vis[d1]) {
            q.push(d1);
            vis[d1] = true;
            prv[d1] = cur;
            type[d1] = 'D';
        }

        int d2 = (cur - 1 + 10000) % 10000;
        if (!vis[d2]) {
            q.push(d2);
            vis[d2] = true;
            prv[d2] = cur;
            type[d2] = 'S';
        }

        int d3 = cur % 1000 * 10 + cur / 1000;
        if (!vis[d3]) {
            q.push(d3);
            vis[d3] = true;
            prv[d3] = cur;
            type[d3] = 'L';
        }

        int d4 = cur % 10 * 1000 + cur / 10;
        if (!vis[d4]) {
            q.push(d4);
            vis[d4] = true;
            prv[d4] = cur;
            type[d4] = 'R';
        }
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    int t;
    cin >> t;

    while (t--) {
        int a, b;
        cin >> a >> b;

        memset(vis, 0, sizeof(vis));
        memset(prv, -1, sizeof(prv));
        memset(type, 0, sizeof(type));
        ans = "";

        bfs(a, b);
        cout << ans << '\n';
    }
}

---