9019번 DSLR
https://www.acmicpc.net/problem/9019
풀이
9019번 DSLR 문제는 두 정수 A에서 B로 변환하기 위한 최소한의 DSLR 연산 순서를 찾는 문제입니다. 이는 전형적인 최단 경로 문제이며, 너비 우선 탐색(BFS)을 통해 해결할 수 있습니다.
BFS 접근 방식:
상태 정의: BFS의 각 상태는 현재 숫자와 해당 숫자에 도달하기까지 사용된 연산 문자열의 쌍
(현재 숫자, 연산 문자열)으로 정의합니다.- 연산 정의:
- D:
n = (2 * n) % 10000- 숫자를 두 배로 늘립니다. 결과가 9999보다 크면 10000으로 나눈 나머지를 취합니다.
- S:
n = (--n < 0?9999:n)- 숫자에서 1을 뺍니다. 결과가 0 미만인 경우 9999로 설정합니다.
- L:
n = (n % 1000) * 10 + n / 1000- 숫자를 왼쪽으로 회전시킵니다. 예를 들어, 1234는 2341이 됩니다.
- 이는
(n을 1000으로 나눈 나머지) * 10(뒤 세 자리를 땡겨오고 0을 붙임) 에n을 1000으로 나눈 몫(맨 앞자리를 맨 뒤로 보냄)을 더하는 방식으로 구현할 수 있습니다.
- R:
n = (n / 10) + (n % 10) * 1000- 숫자를 오른쪽으로 회전시킵니다. 예를 들어, 1234는 4123이 됩니다.
- 이는
(n을 10으로 나눈 몫)(맨 앞 세 자리를 유지) 에(n을 10으로 나눈 나머지) * 1000(맨 뒷자리를 맨 앞으로 보냄)을 더하는 방식으로 구현할 수 있습니다.
- D:
- BFS 구현:
- 큐(Queue) 사용: BFS 탐색을 위해 큐를 사용합니다. 큐에는
(현재 숫자, 연산 문자열)쌍을 저장합니다. - 방문 배열: 이미 방문한 숫자를 기록하기 위해
boolean배열 또는set형태의visited배열을 사용합니다.visited[num]은num에 도달하기 위한 최단 연산 문자열을 저장하거나, 단순히 방문 여부만을 기록할 수 있습니다. 중복 계산 및 무한 루프를 방지합니다. - 초기 상태: 큐에
(시작 숫자 A, "")를 삽입하고,visited[A]를 초기화합니다. - 탐색 과정:
- 큐에서
(현재 숫자, 현재 연산 문자열)을 하나 꺼냅니다. 현재 숫자가목표 숫자 B와 같다면,현재 연산 문자열이 정답이므로 반환하고 탐색을 종료합니다.현재 숫자에 대해 네 가지 DSLR 연산(D, S, L, R)을 각각 적용하여다음 숫자를 계산합니다.- 각
다음 숫자에 대해:- 만약
다음 숫자가 아직 방문하지 않은 숫자라면 (visited배열에서 확인), visited[다음 숫자]를현재 연산 문자열 + 해당 연산 문자로 업데이트하고,- 큐에
(다음 숫자, 현재 연산 문자열 + 해당 연산 문자)를 삽입합니다.
- 만약
- 큐에서
- 큐(Queue) 사용: BFS 탐색을 위해 큐를 사용합니다. 큐에는
시간 복잡도: 이 문제의 상태 공간은 0부터 9999까지의 모든 숫자, 즉 $10^4$개의 노드로 구성됩니다. 각 노드에서 최대 4가지 연산(간선)이 가능합니다. BFS는 모든 노드와 간선을 최대 한 번씩 방문하므로, 시간 복잡도는 $O(V + E)$가 됩니다. 여기서 $V$는 노드의 수 ($10^4$), $E$는 간선의 수 ($4 \times 10^4$)이므로, 전체 시간 복잡도는 $O(10^4)$입니다. 다만, 9019.cpp처럼 큐에 std::string을 저장하고 문자열을 계속 연결하는 경우, 문자열 연결 비용으로 인해 최악의 경우 시간 복잡도가 $O(V \times L_{max})$에 가까워질 수 있습니다. ($L_{max}$는 최장 경로의 길이).
공간 복잡도: BFS에서 큐와 방문 배열(visited 또는 parent/command 배열)에 저장되는 데이터의 양에 따라 공간 복잡도가 결정됩니다. 최대 $10^4$개의 숫자에 대한 정보를 저장해야 하므로, 공간 복잡도는 $O(V)$ 즉, $O(10^4)$입니다. 9019.cpp의 경우 큐에 문자열을 저장하므로 최악의 경우 $O(V \times L_{max})$의 공간을 사용할 수 있습니다.
코드
#include <bits/stdc++.h>
using namespace std;
string BFS(const int a, const int b, const array<function<void(int&)>, 4>& func){
queue<pair<int, string>> q;
q.push({a, ""});
vector<bool> visited(10000, false);
visited[a] = true;
const array<string, 4> DSLR = {"D", "S", "L", "R"};
while(!q.empty()){
auto [curr, exec] = q.front();
q.pop();
if(curr == b)
return exec;
int i = 0;
for(const auto& f: func){
int next = curr;
f(next);
if(!visited[next]){
visited[next] = true;
q.push({next, exec + DSLR[i]});
}
i++;
}
}
return "";
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int iter, regi, a, b;
cin >> iter;
array<function<void(int&)>, 4> func;
func[0] = [](int& n){
n = (n * 2) % 10000;
};
func[1] = [](int& n){
if(--n < 0){
n = 9999;
}
};
func[2] = [](int& n){
n = (n % 1000) * 10 + (n / 1000);
};
func[3] = [](int& n){
n = (n % 10) * 1000 + (n / 10);
};
while(iter--){
cin >> a >> b;
auto res = BFS(a, b, func);
cout << res << endl;
}
return 0;
}최적화
9019.cpp의 비효율성 (개선 전):
- 문자열 연산 오버헤드:
9019.cpp는queue<pair<int, string>> q를 사용하여 큐에 현재 숫자와 함께 현재까지의 연산 문자열exec를 저장합니다. 새로운 노드를 탐색할 때마다exec + DSLR[i]와 같이 문자열을 계속해서 연결합니다. 경로의 길이가 길어질수록 이 문자열 연결 작업은 많은 시간과 메모리를 소모하게 됩니다. 문자열은 변경 불가능하므로, 매번 새로운 문자열이 생성되고 복사되는 오버헤드가 발생합니다. std::function사용:std::function을 사용하여 람다 함수를 저장하고 호출하는 방식은 코드의 가독성을 높일 수 있지만, 일반 함수 호출에 비해 약간의 오버헤드가 발생할 수 있습니다.
9019_optimize.cpp의 최적화 전략 (개선 후):
parent및command배열을 통한 경로 재구성:9019_optimize.cpp는 BFS 탐색 시 경로 문자열을 큐에 함께 저장하지 않습니다. 대신,parent배열과command배열을 활용하여 경로를 재구성합니다.parent[next]는next숫자에 도달하기 바로 전의 숫자(curr)를 저장합니다.command[next]는parent[next]에서next로 이동할 때 사용된 DSLR 명령(문자)을 저장합니다.- BFS가 목표 숫자
b에 도달하면,b부터parent배열을 역추적하여 시작 숫자a까지 거슬러 올라가면서command배열에 저장된 명령들을 역순으로 수집합니다. 마지막에 이 명령 문자열을 뒤집으면 최단 경로가 됩니다. 이 방식은 BFS 탐색 과정에서 문자열 연결로 인한 오버헤드를 완전히 제거하여 성능을 크게 향상시킵니다.
- 간결한
visited상태 관리:parent배열의 값을 -1로 초기화하여 방문 여부를 확인하고, 방문 시parent값을 업데이트하는 방식으로visited배열을 대체합니다. 이 또한 효율적인 메모리 사용과 빠른 접근을 가능하게 합니다. std::function제거: DSLR 연산을 직접 코드 내에서 명시적으로 계산함으로써std::function을 사용하는 데서 오는 작은 오버헤드를 제거합니다.
이러한 최적화 덕분에 9019_optimize.cpp는 9019.cpp에 비해 훨씬 빠른 실행 시간을 보입니다. 다음 이미지를 통해 실행 시간의 차이를 확인할 수 있습니다.
실행 시간 비교
9019.cpp (개선 전): 
9019_optimize.cpp (개선 후): 
위 이미지에서 볼 수 있듯이, 최적화된 버전은 훨씬 빠른 속도로 문제를 해결합니다. 특히 테스트 케이스의 양이 많아지거나 경로가 길어질수록 이러한 최적화의 효과는 더욱 두드러집니다.
최적화 코드
#include <bits/stdc++.h>
using namespace std;
constexpr int MAX = 10000;
void BFS(vector<int>& parent, vector<char>& command, int a, int b){
queue<int> q;
q.push(a);
parent[a] = a;
while(!q.empty()){
int curr = q.front();
q.pop();
if(curr == b)
break;
int D = (curr * 2) % MAX;
if(parent[D] == -1){
parent[D] = curr;
command[D] = 'D';
q.push(D);
}
int S = (curr == 0 ? 9999 : curr-1);
if(parent[S] == -1){
parent[S] = curr;
command[S] = 'S';
q.push(S);
}
int L = (curr % 1000) * 10 + (curr / 1000);
if(parent[L] == -1){
parent[L] = curr;
command[L] = 'L';
q.push(L);
}
int R = (curr % 10) * 1000 + (curr / 10);
if(parent[R] == -1){
parent[R] = curr;
command[R] = 'R';
q.push(R);
}
}
string res = "";
while(b != a){
res += command[b];
b = parent[b];
}
reverse(res.begin(), res.end());
cout << res << '\n';
return;
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int iter, a, b;
cin >> iter;
vector<int> parent(MAX);
vector<char> command(MAX);
while(iter--){
cin >> a >> b;
fill(parent.begin(), parent.end(), -1);
BFS(parent, command, a, b);
}
return 0;
}