BOJ백준 9019 DSLR 풀이(C++)

문제 링크

이번 문제는 BFS 문제이다.

BFS문제는 현재 상태와 다음 상태에 대한 관계를 정의하는 것이 첫 번째라고 볼 수 있다.

이번 문제에서는 현재 상태와 다음 상태는 D S L R로 이루어지는 문자열의 길이로 판가름난다.

예를 들어 현재 상태가 L 이라면 다음으로 갈 수 있는 상태는 LD, LS, LL, LR 이렇게 네 가지이다.

즉 현재가 500이라면 다음 상태는 1000, 499, 5000, (00)50이 되는 것이다.

좀 더 프로그래밍적으로 접근해보자.

예를 들어 초기값이 1234이고 3412를 만든다고 해보자.

먼저 초기값 1234와 빈 문자열을 c++에서 지원하는 자료형인 pair로 묶어 큐에 넣어준다.

그 후 큐(queue)가 빌 때까지 아래와 같이 반복문을 돈다.

1. 의 첫번째 데이터를 가져오고 pop을 한다.

2. 가져온 상태에서 방분한 적이 없고 방문할 수 있는 경우들을 다시 큐에 넣어준다. 큐에 넣어줄 때는 다음  값과 문자열을 다시 pair로 묶어준다.

    이 때 큐에 넣어준 값은 방문함을 나타내는 visited배열에서 해당 인덱스를 true로 만들어준다.

3. 원하는 답을 찾았을 때 break

큐에서 넣었던 데이터를 차례대로 꺼내오기 때문에 같은 depth별로 차례대로 검사하며 내려가게 되고 그렇기 때문에 최초 발견한 값이 최소값이 된다.

소스코드는 아래와 같다.

#include <iostream>
#include <queue>
#include <vector>
 
using namespace std;
int main() {
    int N;
    cin >> N;
    vector<pair<int, int>> Case(N);
    for(int i=0; i<N; i++){
        cin >> Case[i].first >> Case[i].second;
    }
    for(int i=0; i<N; i++){
        queue<pair<int, string>> q;
        vector<bool> visited(10000, 0);
        q.push(make_pair(Case[i].first, ""));
        visited[Case[i].first] = true;
        while(!q.empty()) {
            int now = q.front().first;
            string way = q.front().second;
            q.pop();
            
            if(now == Case[i].second) {
                cout << way << endl;
                break;
            }
            else {
                int next = (now*2) % 10000;
                if(!visited[next]) {
                    visited[next] = true;
                    q.push(make_pair(next, way+"D"));
                }
                if(now == 0) {next = 9999;}
                else {next = now-1;}
                if(!visited[next]) {
                    visited[next] = true;
                    q.push(make_pair(next, way+"S"));
                }
                if(now != 0) {
                    next = (now%1000)*10 + now/1000 ;
                    if(!visited[next]) {
                        visited[next] = true;
                        q.push(make_pair(next, way+"L"));
                    }
                    next = (now/10) + (now%10)*1000;
                    if(!visited[next]) {
                        visited[next] = true;
                        q.push(make_pair(next, way+"R"));
                    }
                }
            }
        }
    }
}
// 해결

지적 및 비판은 언제나 환영입니다. :)