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

문제 링크

---

1. 문제 풀이

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

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

• D: $(n \times 2) \bmod 10000$
• S: $(n - 1 + 10000) \bmod 10000$
• L: $(n \bmod 1000) \times 10 + n / 1000$
• R: $(n \bmod 10) \times 1000 + n / 10$

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

---

2. 코드

1. 풀이 [Java]

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());
        for (int tc = 1; tc <= T; tc++) {
            st = new StringTokenizer(br.readLine());
            int A = Integer.parseInt(st.nextToken());
            int B = Integer.parseInt(st.nextToken());

            String result = bfs(A, B);
            sb.append(result).append("\n");
        }

        System.out.print(sb);
    }

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

        boolean[] visited = new boolean[10000];
        visited[A] = true;

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

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

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

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

            int d1 = node * 2 % 10000;
            if (!visited[d1]) {
                q.offer(d1);
                visited[d1] = true;
                prev[d1] = node;
                type[d1] = 'D';
            }

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

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

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

        return null;
    }
}

2. 풀이 [C++]

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

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

    vector<bool> visited(10000);
    visited[a] = true;

    vector<int> prev(10000, -1);
    vector<char> type(10000);

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

        if (node == b) {
            string res;

            while (prev[node] != -1) {
                res.push_back(type[node]);
                node = prev[node];
            }

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

        int d1 = node * 2 % 10000;
        if (!visited[d1]) {
            q.push(d1);
            visited[d1] = true;
            prev[d1] = node;
            type[d1] = 'D';
        }

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

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

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

    return "";
}

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

    int t;
    cin >> t;

    for (int tc = 1; tc <= t; tc++) {
        int a, b;
        cin >> a >> b;

        string res = bfs(a, b);
        cout << res << '\n';
    }
}

---