Computer >> 컴퓨터 >  >> 프로그래밍 >> Python

C++로 K-유사 문자열의 최소 교환 횟수 K 구하기 (BFS 알고리즘)

문제 개요

두 문자열 s와 t가 있을 때, s에서 임의의 두 문자의 위치를 정확히 K번 교환(swap)하여 t를 만들 수 있다면 이 두 문자열은 K-유사(K-similar)하다고 정의합니다. 서로 애너그램(anagram) 관계인 문자열 s와 t가 주어졌을 때, 두 문자열이 K-유사가 되는 가장 작은 K를 구하는 것이 이 문제의 목표입니다.

예를 들어 s = 'abc', t = 'bac'라고 하면, 앞의 두 글자 'a'와 'b'의 자리를 한 번만 바꾸면 t가 되므로 결과는 1입니다.

접근 방법: 너비 우선 탐색(BFS)

각 교환을 그래프 탐색의 한 단계로 보고, 목표 문자열에 도달할 때까지 레벨별로 확장해 나가는 BFS 방식으로 최소 교환 횟수를 구할 수 있습니다. 탐색 범위를 줄이기 위한 핵심 최적화는 다음 세 가지입니다.

  • 첫 번째 불일치 위치 고정: 현재 문자열과 목표 문자열 B를 왼쪽부터 비교해 처음으로 다른 위치 i를 찾고, 이 위치만 교환 대상으로 삼습니다.
  • 유효한 교환만 시도: curr[j]가 B[i]와 같고, 아직 제자리에 있지 않으며(curr[j] != B[j]), curr[i]와 서로 다른 경우에만 교환합니다. 이미 올바르게 맞춰진 문자는 절대 건드리지 않으므로 불필요한 탐색이 발생하지 않습니다.
  • 방문 상태 관리: unordered_set에 이미 확인한 문자열을 기록해 동일한 상태의 중복 탐색을 방지합니다.

알고리즘 진행 순서

  1. A와 B가 같으면 즉시 0을 반환합니다.
  2. 방문 집합(visited)에 A를 삽입하고, 큐(q)에도 A를 넣습니다.
  3. 레벨(lvl)을 1부터 시작해 큐가 빌 때까지 반복하며, 각 레벨마다 큐에 들어 있는 모든 상태를 처리합니다.
  4. 각 상태에서 첫 번째 불일치 위치 i를 찾은 뒤, j를 i+1부터 끝까지 검사하며 위 조건에 걸리지 않는 쌍(i, j)을 교환합니다.
  5. 교환 결과가 B와 같으면 현재 레벨을 반환하고, 그렇지 않으면 아직 방문하지 않은 상태일 때만 큐에 추가한 후 원래대로 되돌립니다(백트래킹).
  6. 큐가 소진될 때까지 답을 찾지 못하면 -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;
    }
};

int main(){
    Solution ob;
    cout << (ob.kSimilarity("abc", "bac"));
}

실행 결과

입력: 'abc', 'bac'

출력: 1

시간 및 공간 복잡도

문자열 길이를 N이라 할 때, 최악의 경우 탐색해야 하는 상태 수가 문자 치환(permutation)에 비례해 급격히 증가하므로 시간 복잡도는 대략 O(N! × N)입니다. 방문 집합에 저장되는 상태 역시 최대 지수 개수까지 늘어날 수 있어 공간 복잡도도 O(N!) 수준입니다. 다만 불일치 위치를 고정하고 유효한 교환만 시도하는 가지치기 덕분에 실제 탐색 범위는 크게 줄어들어 실용적인 성능을 기대할 수 있습니다.