개요
본 문서에서는 빈 칸(_)의 위치 교환 규칙에 따라 한 문자열을 다른 문자열로 변환할 때 필요한 최소 이동 횟수를 C++의 너비 우선 탐색(BFS)으로 구하는 방법을 다룹니다. 상태 공간을 그래프처럼 탐색하는 대표적인 유형의 문제이므로, BFS와 방문 처리 맵을 함께 활용하는 접근 방식을 자연스럽게 익힐 수 있습니다.
문제 설명
두 문자열 str1과 str2가 주어집니다. 두 문자열은 모두 'a'와 'b' 문자로만 구성되어 있으며 길이가 서로 같고, 각 문자열에는 정확히 하나의 _(빈 칸)가 포함되어 있습니다.
목표는 아래의 연산들을 최소 횟수로 수행하여 첫 번째 문자열을 두 번째 문자열로 변환하는 것입니다.
- 빈 칸(_)이 i번째 위치에 있으면, i+1 또는 i-1 위치의 문자와 맞바꿀 수 있습니다.
- i+1과 i+2 위치의 문자가 서로 다르면, 빈 칸은 i+1 또는 i+2 위치의 문자와 맞바꿀 수 있습니다.
- 마찬가지로 i-1과 i-2 위치의 문자가 서로 다르면, 빈 칸은 i-1 또는 i-2 위치의 문자와 맞바꿀 수 있습니다.
예를 들어 str1 = "aba_a"이고 str2 = "_baaa"라면, 딱 2번의 이동으로 str1을 str2로 변환할 수 있습니다.
1. str1 = "ab_aa" (str1[2]와 str1[3]을 교환)
2. str2 = "_baaa" (str1[0]와 str1[2]를 교환)
알고리즘
- 문자열 위에서 단순 너비 우선 탐색(BFS)을 수행합니다. 큐에 저장되는 원소는 (str, pos) 쌍이며, 여기서 pos는 문자열 str 안에서 빈 칸(_)이 있는 위치입니다.
- 추가로 'vis'라는 맵을 관리하여 문자열을 키로, 해당 문자열에 도달하기까지의 최소 이동 횟수를 값으로 저장합니다.
- 큐에서 꺼낸 각 문자열 str에 대해 앞서 제시된 네 가지 조건에 따라 새로운 문자열 tmp를 생성하고, vis[tmp] = vis[str] + 1로 맵을 갱신합니다.
- 큐가 비거나 목표 문자열(tmp == B)이 만들어질 때까지 위 과정을 반복합니다.
- 목표 문자열이 생성되면 vis[str] + 1을 반환합니다. 이 값이 곧 A를 B로 바꾸는 데 필요한 최소 연산 횟수입니다.
BFS는 시작 상태에서부터 거리가 가까운 순서대로 상태를 탐색하므로, 목표 문자열에 처음 도달했을 때의 이동 횟수가 항상 최소임이 보장됩니다. 또한 'vis' 맵으로 이미 방문한 문자열 상태를 건너뛰기 때문에 동일한 상태를 중복 탐색하지 않아 탐색 효율이 높아집니다.
예제 코드
#include <iostream>
#include <string>
#include <unordered_map>
#include <queue>
using namespace std;
int transformString(string str, string f){
unordered_map<string, int> vis;
int n;
n = str.length();
int pos = 0;
for (int i = 0; i < str.length(); i++) {
if (str[i] == '_') {
pos = i;
break;
}
}
queue<pair<string, int> > q;
q.push({ str, pos });
vis[str] = 0;
while (!q.empty()) {
string ss = q.front().first;
int pp = q.front().second;
int dist = vis[ss];
q.pop();
if (pp > 0) {
swap(ss[pp], ss[pp - 1]);
if (!vis.count(ss)) {
if (ss == f) {
return dist + 1;
break;
}
vis[ss] = dist + 1;
q.push({ ss, pp - 1 });
}
swap(ss[pp], ss[pp - 1]);
}
if (pp < n - 1) {
swap(ss[pp], ss[pp + 1]);
if (!vis.count(ss)) {
if (ss == f) {
return dist + 1;
break;
}
vis[ss] = dist + 1;
q.push({ ss, pp + 1 });
}
swap(ss[pp], ss[pp + 1]);
}
if (pp > 1 && ss[pp - 1] != ss[pp - 2]) {
swap(ss[pp], ss[pp - 2]);
if (!vis.count(ss)) {
if (ss == f) {
return dist + 1;
break;
}
vis[ss] = dist + 1;
q.push({ ss, pp - 2 });
}
swap(ss[pp], ss[pp - 2]);
}
if (pp < n - 2 && ss[pp + 1] != ss[pp + 2]) {
swap(ss[pp], ss[pp + 2]);
if (!vis.count(ss)) {
if (ss == f) {
return dist + 1;
break;
}
vis[ss] = dist + 1;
q.push({ ss, pp + 2 });
}
swap(ss[pp], ss[pp + 2]);
}
}
return 0;
}
int main(){
string str1 = "aba_a";
string str2 = "_baaa";
cout << "Minimum required moves: " << transformString(str1, str2) << endl;
return 0;
}
코드 설명
- 빈 칸 위치 찾기: 먼저 반복문을 돌려 시작 문자열에서 빈 칸(_)의 인덱스를 찾아 초기 상태와 함께 큐에 삽입하고, vis[str] = 0으로 설정합니다.
- 네 가지 이동 시도: 큐에서 현재 상태를 꺼낸 뒤, 왼쪽/오른쪽 인접 교환(pp±1)과 조건부 2칸 교환(pp±2)을 차례로 시도합니다. 2칸 교환은 해당 위치의 두 문자가 서로 다를 때만 허용됩니다.
- 상태 복원: 각 시도 후 swap을 되돌려 원래 문자열을 복원함으로써, 하나의 상태에서 네 가지 분기를 모두 독립적으로 검사할 수 있습니다.
- 목표 확인: 새로 만든 문자열이 목표 문자열 f와 같다면 즉시 dist + 1을 반환하고, 아니면 vis 맵에 기록 후 큐에 추가합니다.
출력 결과
위 프로그램을 컴파일하고 실행하면 다음과 같은 결과가 출력됩니다.
Minimum required moves: 2
결과에서 알 수 있듯이 "aba_a"를 "_baaa"로 변환하는 데 필요한 최소 이동 횟수는 2입니다.