[백준 9019번] [BFS] DSLR

Approach

최소한의 명령어를 찾는 것이므로 BFS를 활용하면 된다는 것을 쉽게 파악할 수 있다. 

https://viyoung.tistory.com/337 이 문제와 접근방법이 매우 유사하다. 

[백준 16397번] [BFS] 탈출

기본적으로 숫자를 기준으로 방문배열을 체크해야한다는 점에서 완전히 동일하다. 다른 지점은, 명령어를 기억해야한다는 점인데 큐에 넣을 때 해당 명령어를 기억하게끔 하면 쉽게 처리할 수 있다.

 

다른 접근 방법으로는 prev 정보를 저장하는 배열을 따로 만들어줘서 LCS처럼 역으로 타고가면서 추적할 수 있다.

해당 방법은 kks227님의 블로그를 참고하도록 하자. https://blog.naver.com/kks227/220785747864

너비 우선 탐색(Breadth-First Search) (수정 2018-11-22)

Code

#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)

using namespace std;

int visited[10001];
string oper[4] = {"D", "S", "L", "R"};

int main(void){
    fastio;
    int t;
    cin >> t;

    while(t--){
        memset(visited, 0, sizeof(visited));
        int a, b;
        cin >> a >> b;
        queue<pair<int, string> > q;
        q.push(make_pair(a, ""));
        visited[a] = 1;
        while(true){
            int cur = q.front().first;
            string cur_oper = q.front().second;
            q.pop();
            if(cur == b){
                cout << cur_oper << "\n";
                break;
            }

            for(int i = 0; i < 4; i++){
                int num = cur;
                if(i == 0) num = (num * 2) % 10000;
                else if(i == 1) num = (num - 1 + 10000) % 10000;
                else if(i == 2) num = (num % 1000) * 10 + num / 1000;
                else num = num / 10 + (num % 10) * 1000;
                if(!visited[num]){
                    q.push(make_pair(num, cur_oper + oper[i]));
                    visited[num] = 1;
                }
            }
        }
    }
    return 0;
}