파이썬(Python)으로 K-유사 문자열의 최소 스왑 횟수 K 구하기

두 문자열 s와 t가 있다고 가정해 보겠습니다. 문자열 s 안에서 두 글자의 위치를 정확히 K번 교환(swap)했을 때 결과가 t와 같아진다면, s와 t는 'K-유사(K-similar)'하다고 정의합니다. 즉, 서로 애너그램(anagram) 관계인 두 문자열 s와 t가 주어졌을 때, 두 문자열이 K-유사가 되도록 만드는 가장 작은 K를 구하는 것이 이 문제의 목표입니다.

예를 들어 s = "abc", t = "bac"라면, 첫 번째 문자 'a'와 두 번째 문자 'b'를 단 한 번만 바꾸면 되므로 출력은 1이 됩니다.

해결 전략: 너비 우선 탐색(BFS)

이 문제는 그래프 탐색 관점에서 접근할 수 있습니다. 현재 문자열 상태에서 한 번의 스왑으로 만들 수 있는 모든 결과를 '이웃(neighbor)' 노드로 보고, 시작점 s에서 목표점 t까지의 최단 거리를 너비 우선 탐색(BFS)으로 찾으면, 그 거리가 곧 최소 스왑 횟수 K가 됩니다.

핵심 아이디어

불일치 지점 찾기: 문자열을 왼쪽부터 훑어 처음으로 t와 다른 위치 i를 찾습니다. 그 앞부분은 이미 올바르게 정렬된 상태이므로 더 이상 건드릴 필요가 없습니다.
후보 스왑 생성: 위치 i 뒤쪽에서 t[i]와 같은 문자가 있는 위치 j를 찾아, i와 j의 문자를 맞바꾼 새 문자열을 후보로 생성합니다.
BFS로 최단 경로 탐색: 큐(queue)에 (문자열, 스왑 횟수) 쌍을 저장하고, 이미 방문한 문자열은 집합(seen)에 기록해 중복 탐색을 방지합니다. t에 도달하는 순간의 스왑 횟수가 곧 정답입니다.

알고리즘 단계

neighbors() 함수를 정의합니다. 이 함수는 현재 문자열에서 가능한 한 번의 스왑 결과들을 차례로 생성(yield)합니다.
new_data의 각 인덱스 i와 문자 c를 순회하면서, c가 t[i]와 다른 첫 번째 위치를 찾으면 반복을 멈춥니다.
i+1부터 문자열 끝까지 j를 순회하며, new_data[j]가 t[i]와 같다면 i와 j의 문자를 교환한 새 문자열을 생성하고, 다시 원래대로 되돌려 다음 후보를 계속 탐색합니다.
메인 로직에서는 큐를 만들어 (s, 0)을 삽입하고, 방문 여부를 기록할 집합 seen을 초기화합니다.
큐가 빌 때까지 반복하며, 큐에서 꺼낸 문자열이 t와 같으면 해당 스왑 횟수를 반환합니다.
그렇지 않으면 neighbors()가 만든 모든 이웃 중 아직 방문하지 않은 것을 큐에 추가합니다.

파이썬 구현 코드

from collections import deque

def solve(s, t):
    # 현재 상태에서 가능한 스왑 후보들을 하나씩 생성하는 제너레이터
    def neighbors(new_data):
        # t와 다른 첫 번째 위치를 찾음
        for i, c in enumerate(new_data):
            if c != t[i]:
                break

        # 그 위치 뒤에서 t[i]와 일치하는 문자를 찾아 스왑
        for j in range(i + 1, len(new_data)):
            if new_data[j] == t[i]:
                new_data[i], new_data[j] = new_data[j], new_data[i]
                yield "".join(new_data)
                new_data[i], new_data[j] = new_data[j], new_data[i]  # 원상 복구

    q = deque([(s, 0)])   # (현재 문자열, 스왑 횟수)
    seen = {s}            # 중복 방문 방지용 집합
    while q:
        u, swap_cnt = q.popleft()
        if u == t:
            return swap_cnt
        for v in neighbors(list(u)):
            if v not in seen:
                seen.add(v)
                q.append((v, swap_cnt + 1))
    return 0

s = "abc"
t = "bac"
print(solve(s, t))

입력 및 출력

입력: s = "abc", t = "bac"

출력: 1

동작 원리 살펴보기

위 예제에서 BFS는 다음과 같이 진행됩니다.

큐에서 ("abc", 0)을 꺼냅니다. "abc"는 "bac"와 다르므로 이웃을 탐색합니다.
t[0] = 'b'와 다른 첫 위치는 인덱스 0입니다. 뒤쪽에서 'b'가 있는 인덱스 1과 스왑하면 "bac"가 생성됩니다.
("bac", 1)이 큐에 추가되고, 다음 반복에서 "bac" == "bac"이므로 스왑 횟수 1이 반환됩니다.

이처럼 BFS는 항상 가장 적은 스왑 횟수로 도달할 수 있는 경로를 먼저 탐색하기 때문에, 처음으로 t에 도달했을 때의 횟수가 곧 최소값 K가 됩니다. 불필요한 스왑을 시도하지 않고 이미 정렬된 앞부분은 건너뛰는 최적화 덕분에 탐색 공간도 크게 줄어듭니다.