양방향 너비 우선 탐색(Bidirectional BFS)은 검색 알고리즘의 고급 최적화 기법으로, 시작점과 목적점이 모두 알려진 경우 최단 경로를 찾는 데 효과적입니다. 전통적인 BFS는 시작점에서만 탐색을 진행하지만, 양방향 BFS는 양쪽에서 동시에 탐색을 진행하여 중간 지점에서 만나는 방식으로 동작합니다. 이 기법은 Meet-in-the-Middle 또는 절반 탐색이라고도 불립니다.
기존의 BFS는 상태 공간이 2^n에 달할 수 있지만, 양방향 BFS를 사용하면 각 방향에서 2^(n/2)만큼의 상태를 탐색하게 되어 전체적으로 제곱근 수준으로 상태 공간이 줄어듭니다. 이는 탐색 속도와 메모리 사용 측면에서 상당한 이점을 제공합니다.
구현 방법
양방향 BFS에는 일반적으로 두 가지 구현 방식이 있습니다:
-
별도 큐 사용: 정방향 BFS와 역방향 BFS를 각각 다른 큐에서 관리합니다. 이 방법은 정방향과 역방향 탐색의 상태 수가 불균형할 때 효과적입니다. 상태 수가 적은 방향부터 먼저 확장하여 더 빠른 만남을 유도할 수 있습니다. 예를 들어, 문자열 변환 문제에서 유용하게 적용됩니다.
-
공용 큐 사용: 정방향과 역방향 BFS를 동일한 큐에서 관리합니다. 이 방법은 두 방향의 확장 상태 수가 비슷할 때 적합합니다. 두 방향의 탐색을 번갈아 가며 수행하여 만남을 확인합니다. 예를 들어, 8-퍼즐 문제에서 주로 사용됩니다.
일반 BFS와 마찬가지로, 양방향 BFS에서도 중복 상태 처리가 필요합니다. 큐에 상태를 추가하기 전에 이미 방문했는지 확인하여 중복을 방지합니다.
문자열 변환 문제
문제 분석: A 문자열을 B 문자열로 변환하는 최소 단계를 찾는 문제입니다. 양방향 BFS를 적용하여 양쪽에서 변환 규칙을 적용하며 탐색합니다. 각 상태에서 변환 규칙을 적용하여 새로운 상태를 생성하고, map을 사용하여 각 상태의 깊이를 기록합니다.
#include <iostream>
#include <queue>
#include <map>
#include <string>
using namespace std;
int ruleCount = 1;
string startRules[10], endRules[10];
string startStr, endStr;
int expand(queue<string>& q, map<string, int>& dist, map<string, int>& otherDist,
string rules[], string otherRules[]) {
string current = q.front();
q.pop();
for (int i = 0; i < current.size(); i++) {
for (int j = 1; j <= ruleCount; j++) {
if (current.substr(i, rules[j].size()) == rules[j]) {
string next = current.substr(0, i) + otherRules[j] + current.substr(i + rules[j].size());
if (dist.find(next) != dist.end()) continue;
if (otherDist.find(next) != otherDist.end()) {
return dist[current] + 1 + otherDist[next];
}
dist[next] = dist[current] + 1;
q.push(next);
}
}
}
return 11;
}
int findMinTransformations(string a, string b) {
queue<string> q1, q2;
map<string, int> dist1, dist2;
q1.push(a); dist1[a] = 0;
q2.push(b); dist2[b] = 0;
while (!q1.empty() && !q2.empty()) {
int result;
if (q1.size() <= q2.size()) {
result = expand(q1, dist1, dist2, startRules, endRules);
} else {
result = expand(q2, dist2, dist1, endRules, startRules);
}
if (result <= 10) return result;
}
return 11;
}
int main() {
cin >> startStr >> endStr;
while (cin >> startRules[ruleCount] >> endRules[ruleCount]) {
ruleCount++;
}
int answer = findMinTransformations(startStr, endStr);
if (answer > 10) {
cout << "NO ANSWER!" << endl;
} else {
cout << answer << endl;
}
return 0;
}
8-퍼즐 문제
문제 분석: 8-퍼즐은 3x3 그리드에서 1부터 8까지의 숫자와 하나의 빈 칸을 이동시켜 목표 상태를 만드는 문제입니다. 양방향 BFS를 사용하여 시작 상태와 목표 상태에서 동시에 탐색을 진행합니다. 각 상태를 정수로 표현하여 효율적으로 관리합니다.
#include <iostream>
#include <queue>
#include <map>
using namespace std;
const int target = 123804765;
int startState;
int moves[4][2] = {{0, 1}, {1, 0}, {-1, 0}, {0, -1}};
int grid[5][5];
map<int, int> visited, distance;
int bfs(int start, int end) {
queue<int> q;
visited[start] = 1;
visited[end] = 2;
distance[start] = 0;
distance[end] = 0;
q.push(start);
q.push(end);
while (!q.empty()) {
int current = q.front();
q.pop();
int temp = current;
int x, y;
// 숫자를 그리드에 배치
for (int i = 3; i >= 1; i--) {
for (int j = 3; j >= 1; j--) {
grid[i][j] = temp % 10;
temp /= 10;
if (grid[i][j] == 0) {
x = i;
y = j;
}
}
}
// 빈 칸을 이동
for (int i = 0; i < 4; i++) {
int nx = x + moves[i][0];
int ny = y + moves[i][1];
if (nx < 1 || nx > 3 || ny < 1 || ny > 3) continue;
swap(grid[x][y], grid[nx][ny]);
// 상태를 정수로 변환
int newState = 0;
for (int i = 1; i <= 3; i++) {
for (int j = 1; j <= 3; j++) {
newState = newState * 10 + grid[i][j];
}
}
if (visited[newState] == visited[current]) {
swap(grid[x][y], grid[nx][ny]);
continue;
}
if (visited[newState] + visited[current] == 3) {
return distance[current] + 1 + distance[newState];
}
distance[newState] = distance[current] + 1;
visited[newState] = visited[current];
q.push(newState);
swap(grid[x][y], grid[nx][ny]);
}
}
return -1;
}
int main() {
cin >> startState;
if (startState == target) {
cout << 0 << endl;
} else {
cout << bfs(startState, target) << endl;
}
return 0;
}
회전 퍼즐 문제
문제 분석: 회전 퍼즐은 최대 20번의 회전 연산을 통해 주어진 패턴을 목표 패턴으로 만드는 문제입니다. 단방향 탐색은 4^20으로 너무 크므로 양방향 BFS를 적용합니다. 각 방향의 최대 깊이를 10으로 제한하여 상태 수를 획기적으로 줄입니다.
#include <iostream>
#include <queue>
#include <map>
#include <string>
using namespace std;
const int MAX = 10;
int rows, cols;
int original[MAX][MAX], temp[MAX][MAX], countNum[MAX*MAX];
int rotationPatterns[4][3] = {{1, 1}, {0, 1}, {1, 0}, {0, 0}};
string startState, targetState;
map<string, int> visited, distances;
string rotate(int x, int y) {
string result;
for (int i = 1; i < rows; i++) {
for (int j = 1; j < cols; j++) {
temp[i+x][j+y] = original[rows-i+x][cols-j+y];
}
}
for (int i = 1; i <= rows; i++) {
for (int j = 1; j <= cols; j++) {
result += temp[i][j] + '0';
}
}
return result;
}
void restore(string state) {
for (int i = 1; i <= rows; i++) {
for (int j = 1; j <= cols; j++) {
temp[i][j] = original[i][j] = state[(i-1)*cols + (j-1)] - '0';
}
}
}
int solve(string start, string target) {
queue<string> q;
q.push(start);
q.push(target);
visited[start] = 1;
distances[start] = 0;
visited[target] = 2;
distances[target] = 0;
while (!q.empty()) {
string current = q.front();
q.pop();
for (int i = 0; i < 4; i++) {
restore(current);
int offsetX = rotationPatterns[i][0];
int offsetY = rotationPatterns[i][1];
string newState = rotate(offsetX, offsetY);
if (visited[newState] == visited[current]) continue;
if (visited[newState] + visited[current] == 3) {
return distances[newState] + 1 + distances[current];
}
distances[newState] = distances[current] + 1;
if (distances[newState] > 10) return 21;
visited[newState] = visited[current];
q.push(newState);
}
}
return 21;
}
int main() {
cin >> rows >> cols;
for (int i = 1; i <= rows; i++) {
for (int j = 1; j <= cols; j++) {
cin >> original[i][j];
startState += original[i][j] + '0';
countNum[original[i][j]]++;
}
}
for (int i = 1; i <= rows*cols; i++) {
if (countNum[i] != 1) {
cout << -1 << endl;
return 0;
}
targetState += i + '0';
}
if (targetState == startState) {
cout << 0 << endl;
return 0;
}
int answer = solve(startState, targetState);
if (answer > 20) {
cout << -1 << endl;
} else {
cout << answer << endl;
}
return 0;
}