문제 소개
두 문자열 A와 B가 있다고 가정해 보겠습니다. 문자열 A에서 임의의 두 글자의 위치를 정확히 K번 교환(swap)했을 때 결과가 B와 같아진다면, 이 두 문자열은 K-유사(K-similar)하다고 정의합니다. 여기서 K는 음수가 아닌 정수입니다.
즉, 서로 애너그램(anagram) 관계인 두 문자열 A와 B가 주어졌을 때, 두 문자열이 K-유사 관계가 되도록 하는 최소값 K를 찾는 것이 이 문제의 핵심입니다.
예를 들어 입력이 A = "abc", B = "bac"라고 해보죠. 인덱스 0의 'a'와 인덱스 1의 'b'를 딱 한 번만 교환하면 "abc"가 "bac"로 변하므로, 정답은 1입니다.
풀이 접근 방법: 너비 우선 탐색(BFS)
이 문제는 너비 우선 탐색(BFS)을 활용하면 효율적으로 해결할 수 있습니다. 각 문자열 상태를 그래프의 노드로 보고, 한 번의 스왑으로 도달 가능한 상태들을 간선으로 연결한다고 생각하면, 시작 문자열 A에서 목표 문자열 B까지의 최단 거리가 곧 최소 교환 횟수 K가 됩니다.
탐색 범위를 줄이기 위해 다음과 같은 가지치기(pruning) 기법을 함께 사용합니다.
- 첫 불일치 위치 고정: 현재 문자열과 B를 비교해 처음으로 다른 위치 i를 찾고, 그 위치부터만 스왑을 시도합니다. 이미 일치하는 앞부분은 절대 건드리지 않습니다.
- 조건 필터링: curr[j]가 B[i]와 다르거나, curr[j]가 이미 B[j]와 일치한다면 그런 스왑은 무의미하므로 건너뜁니다.
- 방문 처리: 이미 탐색한 문자열 상태는 집합(visited)에 기록해 중복 탐색을 방지합니다.
알고리즘 단계
- 두 위치의 문자를 교환하는 보조 함수
swapp()를 정의합니다. 문자열 s와 인덱스 i, j를 받아 s[i]와 s[j]의 값을 서로 맞바꿉니다. - A와 B가 같다면 즉시 0을 반환합니다.
- 방문 집합 visited를 만들어 A를 삽입하고, 큐 q에도 A를 넣습니다.
- 레벨(lvl)을 1부터 시작해 큐가 빌 때까지 반복하며, 각 레벨마다 큐에 들어 있는 모든 상태(sz개)를 처리합니다.
- 각 상태 curr에 대해 다음을 수행합니다.
- i를 0부터 늘려가며 curr[i] != B[i]가 되는 첫 번째 위치를 찾습니다.
- j를 i+1부터 끝까지 순회하며, curr[i] == curr[j], curr[j] != B[i], curr[j] == B[j] 세 가지 경우는 건너뜁니다.
- 조건을 통과하면 swapp(curr, i, j)로 스왑한 뒤, curr == B라면 현재 lvl을 반환합니다.
- curr를 아직 방문하지 않았다면 visited에 추가하고 큐에 삽입합니다.
- 다음 j 후보를 탐색하기 위해 다시 swapp(curr, i, j)로 원상 복구합니다(백트래킹).
- BFS가 종료될 때까지 답을 찾지 못하면 -1을 반환합니다.
C++ 구현 코드
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int kSimilarity(string A, string B) {
if (A == B)
return 0;
unordered_set<string> visited;
visited.insert(A);
queue<string> q;
q.push(A);
for (int lvl = 1; !q.empty(); lvl++) {
int sz = q.size();
while (sz--) {
string curr = q.front();
q.pop();
int i = 0;
while (i < curr.size() && curr[i] == B[i])
i++;
for (int j = i + 1; j < curr.size(); j++) {
if (curr[i] == curr[j])
continue;
if (curr[j] != B[i])
continue;
if (curr[j] == B[j])
continue;
swapp(curr, i, j);
if (curr == B)
return lvl;
if (!visited.count(curr)) {
visited.insert(curr);
q.push(curr);
}
swapp(curr, i, j);
}
}
}
return -1;
}
void swapp(string &s, int i, int j) {
char x = s[i];
char y = s[j];
s[i] = y;
s[j] = x;
}
};
main(){
Solution ob;
cout << (ob.kSimilarity("abc", "bac"));
}
실행 결과
입력: "abc", "bac"
출력: 1
마무리
이 풀이의 시간 복잡도는 이론상 최악의 경우 지수적으로 증가할 수 있지만, 위에서 설명한 가지치기 덕분에 실제 동작 속도는 훨씬 빠릅니다. 특히 "첫 불일치 위치 고정" 전략은 탐색해야 할 상태 공간을 크게 줄여 주는 핵심 요소입니다. 또한 BFS를 레벨 단위로 순회하기 때문에 목표 문자열 B에 도달하는 순간의 레벨 값이 곧 최소 교환 횟수임이 자연스럽게 보장됩니다.