백준 9019번 [DSLR](C++)-yes6686- 티스토리

백준 문제 풀이: 9019 [DSLR]

---

문제 링크: https://www.acmicpc.net/problem/9019

문제 설명:

주어진 정수 A를 B로 변환하기 위해 네 가지 연산(D, S, L, R)을 사용합니다. 각 연산은 다음과 같습니다:

• D: 2를 곱한 결과를 10000으로 나눈 나머지
• S: A에서 1을 뺀 결과 (A가 0이면 9999)
• L: A의 각 자릿수를 왼쪽으로 회전
• R: A의 각 자릿수를 오른쪽으로 회전

A를 B로 변환하는 가장 짧은 명령어를 출력하는 문제입니다. 여러 가지 방법이 있을 경우 사전 순으로 가장 앞서는 결과를 출력합니다.

---

문제 해결 코드

#include <iostream>
#include <string>
#include <string.h>
#include <queue>
using namespace std;

queue<pair<int, string>> q;
int visited[10001];
int a, b;

void bfs() {
    while (!q.empty()) {
        int kx = q.front().first;
        string op = q.front().second;
        if (kx == b) {
            cout << op << '\n';
            return;
        }
        q.pop();

        int nx;
        // D 연산
        nx = (2 * kx) % 10000;
        if (!visited[nx]) {
            visited[nx] = 1;
            q.push({nx, op + "D"});
        }
        // S 연산
        nx = (kx == 0) ? 9999 : kx - 1;
        if (!visited[nx]) {
            visited[nx] = 1;
            q.push({nx, op + "S"});
        }
        // L 연산
        nx = (kx % 1000) * 10 + (kx / 1000);
        if (!visited[nx]) {
            visited[nx] = 1;
            q.push({nx, op + "L"});
        }
        // R 연산
        nx = (kx % 10) * 1000 + (kx / 10);
        if (!visited[nx]) {
            visited[nx] = 1;
            q.push({nx, op + "R"});
        }
    }
}

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

    int T;
    cin >> T;
    while (T--) {
        cin >> a >> b;
        q.push({a, ""});
        visited[a] = 1;
        bfs();
        memset(visited, 0, sizeof(visited));
        while (!q.empty()) q.pop();
    }
    return 0;
}

---

코드 설명

• 핵심 알고리즘: BFS(너비 우선 탐색)를 사용하여 최소 연산 경로를 탐색합니다.
• 구현 세부사항:
  • 큐에 현재 숫자와 연산 문자열을 함께 저장하여 상태를 관리합니다.
  • 네 가지 연산을 적용하고, 방문하지 않은 숫자라면 큐에 추가합니다.
  • 목표 숫자 B에 도달하면 연산 문자열을 출력합니다.
  • 테스트 케이스가 여러 개인 경우, 각 케이스마다 방문 배열과 큐를 초기화합니다.
• 시간 복잡도: O(10000) (최대 10000개의 상태를 BFS로 탐색)

---

결과

주어진 A에서 B로 변환하는 가장 짧은 연산 문자열을 출력합니다. BFS를 사용하여 모든 가능한 상태를 탐색하고, 최적 경로를 찾습니다.

다른 접근 방식이나 개선 사항이 있다면 댓글로 공유 부탁드립니다!