BFS - 단어 변환

문제 :

이 문제를 보고 BFS인지 떠올릴 수 있는 요소들 :

1. 최단 변환 과정 찾기: 문제에서 요구하는 것은 ‘가장 짧은 변환 과정’을 찾는 것이다. BFS는 레벨별로 모든 가능성을 탐색하며, 이 과정에서 각 단계의 모든 가능한 경우를 고려하기 때문에 최단 경로를 보장한다.

2. 한 번에 한 글자만 바꿀 수 있는 규칙: 이 규칙은 각 단계에서 가능한 모든 변환을 시도해볼 수 있게 하며, BFS는 이러한 시도를 체계적으로 관리하여 가장 빠른 결과를 도출할 수 있게 한다.

3. words 리스트의 제한된 크기: BFS는 상대적으로 제한된 범위 내에서 효과적으로 작동한다. words의 크기가 50개 이하로 제한되어 있어, BFS를 사용할 경우 너무 많은 메모리를 소모하거나 시간이 과도하게 걸리는 문제를 피할 수 있다.

 

BFS는 큐, DFS는 스택, 재귀를 기반으로 동작한다. 아래 코드를 살펴보자.

from collections import deque

def solution(begin, target, words):
    if target not in words:
        return 0
    queue = deque()
    queue.append((begin, 0))
    visited = set()
    
    while queue:
        curr, steps = queue.popleft()
        if curr == target:
            return steps
        for word in words:
            if word not in visited and sum([c1 != c2 for c1, c2 in zip(curr, word)]) == 1:
                visited.add(word)
                queue.append((word, steps + 1))
    return 0

 

우선, 타겟이 words배열에 없으면 아예 검사 자체를 할 필요가 없으므로 맨 앞단에 이 조건문을 넣어 이 조건이 fail하면 곧바로 끝내도록 한다.

 

다음으로, BFS에서 사용될 큐를 만들어준다. 다음으로, 처음 검사될 단어 begin과 변환 횟수 0 을 튜플에 담아 큐에 넣어준다. 다음으로, 이미 방문한 노드(word)를 재방문 하지 않기 위한 visited를 만든다. 또한, BFS에서는 이 visited가 최단 경로를 보장 해준다. 

 

만약, 타겟 단어가 words배열 안에 존재한다면, while문으로 넘어간다.

 

while queue: 큐에 요소가 하나라도 있는동안,

 

큐에서 요소를 하나 꺼내어 현재 단어(curr), 몇 단계를 거쳐 단어가 변환 되었는지를 나타내는 steps 변수에 할당한다. 만약, 꺼낸 단어가 타겟과 같다면 바로 스텝을 리턴한다. 

 

아니라면, words의 단어들을 하나씩 순회하며 이 단어가 '방문된 적이 없고', 문제의 핵심 조건중 하나인 "단 한가지 단어만 바꿀 수 있다면"을 검사해야 한다. 두개의 단어가 철자 하나만 빼고 모두 같은지 가장 쉽고 빠르게 확인하는 방법은 문자열에 zip을 사용하는것이다. 저 짧은 if문 안에 3개의 스킬(?)이 들어갔다.

 

1. 리스트 컴프리헨션

2. 문자열 zip

3. True == 1, False == 0

 

우선, 

sum([c1 != c2 for c1, c2 in zip(curr, word)])

 

zip 함수를 문자열에 사용하여 두 문자열 간의 다른 문자를 찾는 방법은 매우 유용하다. 이를 통해 한 단어에서 다른 단어로의 변환이 한 글자만 다른지 쉽게 확인할 수 있다.

 

문자열에서의 zip 활용 예

 

curr = "hit", word = "hot"의 예를 들면, zip("hit", "hot")은 각 문자를 인덱스 별로 묶어서 [(h, h), (i, o), (t, t)]과 같은 튜플의 리스트를 생성한다. 이 튜플에서 첫 번째 요소는 c1, 두 번째 요소는 c2로 할당된다.

 

문자 비교와 리스트 컴프리헨션

 

리스트 컴프리헨션 c1 != c2는 각 튜플을 비교하여, 두 문자가 다르면 True, 같으면 False를 반환한다. 따라서 위 예에서는 [False, True, False] 리스트가 생성된다. 이 리스트는 각 문자 위치에서 문자가 같은지 다른지를 나타낸다.

 

True와 False의 수치 계산

 

파이썬에서는 True와 False를 각각 1과 0으로 처리할 수 있다. 이 특성 덕분에 sum([False, True, False]) 호출이 가능하며, 이는 1을 반환한다. 이는 “hit”와 “hot” 사이에 정확히 한 글자만 다름을 의미한다.

 

BFS에서의 활용

 

이 기능을 BFS 탐색에 적용할 때, 큐에서 현재 단어를 꺼내고 이와 한 글자만 다른 모든 단어를 찾아내는 과정에서 중요하게 사용된다. 만약 해당 단어가 방문하지 않은 단어이고 한 개의 문자만 다르다면, 이 단어는 방문 대상으로 간주되어 방문 기록에 추가되고, 큐에는 이 단어와 현재 단계 수에서 1을 더한 값이 함께 저장된다.

 

이러한 절차를 통해 BFS는 각 단계마다 가능한 모든 경로를 탐색하며, 최초로 목표 단어에 도달할 때 그 경로가 최단 경로임을 보장한다. 각 단어는 처음 방문될 때 가장 적은 수의 변환을 거쳐 도달했으므로, 이후에 같은 단어에 도달하는 다른 경로는 더 많은 변환을 필요로 하여 고려되지 않는다.