[Python][C++] 9019번 DSLR

문제

https://www.acmicpc.net/problem/9019

 

 

 

 

코드

1. Python

from collections import deque

# 각 명령어의 동작을 정의하는 함수들
def D(x):
    return (x * 2) % 10000  # D 명령어: x를 두 배로 만든 후 10000으로 나눈 나머지

def S(x):
    return x - 1 if x > 0 else 9999  # S 명령어: x에서 1을 뺀 값, x가 0이면 9999로 설정

def L(x):
    return (x % 1000) * 10 + x // 1000  # L 명령어: x를 왼쪽으로 회전 (십진수 자릿수 이동)

def R(x):
    return (x % 10) * 1000 + x // 10  # R 명령어: x를 오른쪽으로 회전 (십진수 자릿수 이동)

# BFS 탐색을 통한 최단 경로 탐색 함수
def bfs(x, target):
    op = [D, S, L, R]  # 명령어 함수 리스트
    label = ['D', 'S', 'L', 'R']  # 명령어를 나타내는 문자열 리스트
    visited = [-1] * 10000  # 방문 여부를 표시하는 리스트, 초기값은 -1
    q = deque([(x, "")])  # BFS를 위한 큐, (현재값, 명령어 경로)로 구성된 튜플을 저장
    
    visited[x] = 1  # 시작점 방문 표시

    # BFS 시작
    while q:
        curr, route = q.popleft()  # 큐에서 현재 상태와 명령어 경로를 꺼냄

        if curr == target:  # 목표 값에 도달하면 명령어 경로를 반환
            return route

        # 네 가지 명령어를 각각 적용
        for i in range(4):
            nx = op[i](curr)  # 현재 상태에 명령어를 적용하여 새로운 상태 생성

            if visited[nx] == -1:  # 아직 방문하지 않은 상태라면
                q.append((nx, route + label[i]))  # 새로운 상태와 경로를 큐에 추가
                visited[nx] = 1  # 방문 표시

    return ""  # BFS가 끝나도록 목표에 도달하지 못하면 빈 문자열 반환 (사실상 발생하지 않음)

# 메인 함수
def main():
    t = int(input())  # 테스트 케이스의 수 입력
    
    for _ in range(t):  # 각 테스트 케이스에 대해
        a, b = map(int, input().split())  # 초기 값 a와 목표 값 b 입력
        print(bfs(a, b))  # a에서 b로 변환하는 최단 명령어 경로 출력

# 메인 함수 호출
if __name__ == "__main__":
    main()

 

2. C++

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

using namespace std;

// 각 명령어에 해당하는 함수들
int D(int x) {
    return (x * 2) % 10000;  // D: x를 두 배로 만들고 10000으로 나눈 나머지
}

int S(int x) {
    return (x > 0) ? x - 1 : 9999;  // S: x에서 1을 빼고, 0이면 9999로
}

int L(int x) {
    return (x % 1000) * 10 + x / 1000;  // L: 자릿수를 왼쪽으로 회전
}

int R(int x) {
    return x / 10 + (x % 10) * 1000;  // R: 자릿수를 오른쪽으로 회전
}

// BFS를 통해 최단 경로를 찾는 함수
string bfs(int x, int target) {
    int (*op[4])(int x) = {D, S, L, R};  // D, S, L, R 함수 포인터 배열
    char label[4] = {'D', 'S', 'L', 'R'};  // 각 함수에 대응하는 명령어 문자
    vector<int> visited(10000, -1);  // 방문 여부를 체크하는 배열, 초기값 -1
    queue<pair<int, string>> q;  // BFS 탐색을 위한 큐, (현재 값, 경로)

    q.push(make_pair(x, ""));  // 시작 값을 큐에 추가
    visited[x] = 1;  // 시작 값 방문 처리

    while (!q.empty()) {
        int curr = q.front().first;  // 현재 값
        string route = q.front().second;  // 현재까지의 경로
        q.pop();

        if (curr == target)  // 목표 값에 도달했으면 경로 반환
            return route;

        // D, S, L, R 명령어를 차례로 적용
        for (int i = 0; i < 4; i++) {
            int nx = op[i](curr);  // 새로운 값 계산

            if (visited[nx] == -1) {  // 방문하지 않은 값이라면
                q.push(make_pair(nx, route + label[i]));  // 큐에 추가
                visited[nx] = 1;  // 방문 처리
            }
        }
    }

    return "";  // 이론상 이 코드에선 도달하지 않음
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    
    int t;
    cin >> t;  // 테스트 케이스 수 입력

    while (t--) {
        int a, b;
        cin >> a >> b;  // 시작 값과 목표 값 입력
        cout << bfs(a, b) << "\n";  // BFS를 통해 최단 경로 출력
    }

    return 0;
}

 

 

풀이 

 

1. BFS 사용:
   • B각 상태(숫자)를 정점으로, 가능한 변환을 간선으로 생각하여 그래프로 표현
   • 숫자 A에서 시작하여 숫자 B에 도달할 때까지 BFS를 통해 가능한 모든 경로를 탐색
2. 상태 저장 및 방문 체크:
   • 숫자 변환 과정에서 동일한 숫자가 다시 등장하지 않도록 방문한 숫자 체크
   • 각 숫자에 대해 해당 숫자까지 어떻게 도달했는지를 저장
3. 명령어 적용:
   • 각 숫자에 대해 가능한 네 가지 명령(D, S, L, R)을 차례대로 적용하여 다음 숫자를 생성
   • 생성된 숫자가 목표 숫자 B와 일치하면, 해당 경로를 출력하고 BFS를 종료
4. 결과 도출:
   • BFS가 끝나면 목표 숫자 B에 도달하는 최소 경로를 출력

 

 

https://ehdbs0903.tistory.com/entry/Algorithm-너비-우선-탐색-BFSBreadth-First-Search-알고리즘

[Algorithm] 너비 우선 탐색 / BFS(Breadth-First Search) 알고리즘