파이썬으로 철자가 틀린 단어를 고치는 데 필요한 최소 문자 변경 횟수 찾기

도시 목록과 도시들을 연결하는 도로 목록이 주어진 상황을 가정해 보겠습니다. 'cities' 리스트에는 관광 버스가 순서대로 방문하는 도시 이름들이 담겨 있고, 'roads' 리스트에는 (출발지, 도착지) 순서로 도로 정보가 기록되어 있습니다. 즉, 출발지에서 도착지로 향하는 일방통행 도로를 의미합니다.

그런데 문제는 'cities' 리스트의 일부 도시 이름에 철자 오류가 있을 수 있다는 점입니다. 우리는 이렇게 잘못 입력된 도시 이름을 최소한의 문자 변경만으로 올바른 이름으로 교정해야 하며, 실제로 변경된 문자의 개수를 결과로 반환해야 합니다.

예를 들어, 입력이 다음과 같다고 가정해 보겠습니다.

cities = ["HWH", "DLI", "BGL"]
roads = [["HWH", "DLI"], ["DLI", "BCT"], ["BCT", "HWH"]]

이 경우 출력은 2가 됩니다. 'cities'에서 철자가 틀린 이름은 'BGL'이며, 올바른 이름은 'BCT'입니다. 'BGL'을 'BCT'로 고치려면 두 글자(G→C, L→T)를 변경해야 하므로 정답은 2입니다.

해결 접근 방법

이 문제는 동적 계획법(DP)과 유사한 방식으로 해결할 수 있습니다. 핵심 아이디어는 각 방문 단계마다 도달 가능한 모든 도시를 추적하면서, 해당 도시에 도달하기까지 누적된 문자 변경 비용을 기록하고, 마지막에 그중 최솟값을 선택하는 것입니다.

단계별로 살펴보면 다음과 같습니다.

diff() 함수 정의: 두 문자열 a, b를 받아 서로 다른 문자의 개수를 반환합니다.
size := cities의 크기
arr := 새로운 맵(딕셔너리)
junctions := roads에 등장하는 각 출발 도시들의 집합
junctions의 각 j에 대해 arr[j] := diff(cities[0], j)를 저장합니다. 즉, 첫 번째 방문 도시와의 차이를 초기 비용으로 설정합니다.
i가 1부터 size까지 반복합니다.
- nxt := 새로운 맵
- roads의 각 (r1, r2)에 대해:
  - r1이 arr에 존재하면:
    - cost := arr[r1] + diff(cities[i], r2)
    - r2가 nxt에 없거나 cost가 nxt[r2]보다 작으면 nxt[r2] := cost로 갱신합니다.
- arr := nxt로 교체하여 다음 단계로 진행합니다.
마지막으로 arr의 모든 값 중 최솟값을 반환합니다.

이 과정은 본질적으로 각 도로를 간선으로, 문자 변경 횟수를 가중치로 보는 최단 경로 탐색과 같습니다. 매 단계에서 불필요한 경로는 버리고 더 적은 비용의 경로만 유지하기 때문에 효율적으로 동작합니다.

구현 예제

다음 파이썬 구현을 통해 더 자세히 이해해 보겠습니다.

def diff(a, b):
    return sum(x != y for x, y in zip(a, b))

def solve(cities, roads):
    size = len(cities)
    arr = dict()
    junctions = set(r[0] for r in roads)
    for j in junctions:
        arr[j] = diff(cities[0], j)
    for i in range(1, size):
        nxt = dict()
        for r1, r2 in roads:
            if r1 in arr:
                cost = arr[r1] + diff(cities[i], r2)
                if r2 not in nxt or cost < nxt[r2]:
                    nxt[r2] = cost
        arr = nxt
    return min(arr.values())

print(solve(["HWH", "DLI", "BGL"], [["HWH", "DLI"],["DLI", "BCT"],
["BCT", "HWH"]]))

입력

["HWH", "DLI", "BGL"], [["HWH", "DLI"],["DLI", "BCT"], ["BCT",
"HWH"]]

출력

여기서 사용된 diff() 함수는 zip()으로 두 문자열을 글자 단위로 묶은 뒤, 서로 다른 위치의 개수를 합산하는 간결한 방식으로 편집 거리(해밍 거리)를 계산합니다. 두 문자열의 길이가 같다는 전제하에 이 방법이 유효하며, 이 문제에서는 모든 도시 코드가 같은 길이를 가지므로 문제없이 적용됩니다.