백준 9019 - DSLR [C/C++] 백트래킹 알고리즘

9019번: DSLR (acmicpc.net)

9019번: DSLR

문제 설명은 다음과 같다.

문제 설명 / 입력 / 출력

예제 입력 / 예제 출력

 

평범한 BFS 문제지만, 조건을 하나 정해줘서 경로가 끊겼다면 더 이상 탐색하지 않게 막아주는 분기가 필요하다.

 

• Visited 배열을 하나 생성해주자. 최대값은 10000이니 visited[10000]으로 선언.
• DSLR을 통해 한 번 방문한 문자열의 visited는 True로 처리해주고, 이후에 다시 방문한다면 걸러주자
  • why? -> 이후에 방문한 것은 어차피 전에 방문했다면 그것보다 무조건 더 긴 DSLR 문자열을 가질테니 최솟값이 될 수 없다!
• Queue에서 계속 빼주면서, 각각의 D, S, L, R 값을 계산 후 큐에 다시 넣어준다.
• empty가 되거나, 찾고 있는 target 값이 등장한다면 break!

아래는 위 사고 구조를 그대로 구현한 C++ 코드이다.

#include <iostream>
#include <algorithm>
#include <queue>
#include <string>
#include <cstring>
#define fastcpp ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)

using namespace std;
int test_case;
int current, target;
bool visited[10000];

void bfs(){
    queue<pair<int,string>> q;
    q.push({current,""});
    while(!q.empty()){
        int cur = q.front().first;
        string DSLR = q.front().second;
        q.pop();
        if (cur==target) {
            cout << DSLR << '\n';
            return;
        }
        int DValue = (cur*2)%10000;
        int SValue = (cur-1<0) ? 9999 : cur-1;
        int LValue =(cur % 1000) * 10 + (cur / 1000);
        int RValue = cur / 10 + (cur % 10) * 1000;
        if (!visited[DValue]){
            visited[DValue] = true;
            q.push({DValue,DSLR+'D'});
        }
        if (!visited[SValue]){
            visited[SValue] = true;
            q.push({SValue,DSLR+'S'});
        }
        if (!visited[LValue]){
            visited[LValue] = true;
            q.push({LValue,DSLR+'L'});
        }
        if (!visited[RValue]) {
            visited[RValue] = true;
            q.push({RValue,DSLR+'R'});
        }
    }
}

int main() {
    fastcpp;
    cin >> test_case;
    while(test_case>0){
        test_case--;
        cin >> current >> target;
        memset(visited, false, sizeof(visited));
        bfs();
    }
    return 0;
}