[프로그래머스] 단어 변환(LV3 - Python)

프로그래머쓱

해당 글에서는 단어 변환 문제를 Python을 이용해 풀이하고자 한다.

프로그래머스

 

🔷 문제 설명

 

🔷 문제 풀이

처음엔 완전 탐색을 이용해 문제를 푸려고 했다.

combination을 이용해 words의 방문 순서를 정하고, 방문 순서에 따라 한 글자씩 차이나는지 아닌지를 통해 모든 경우를 탐색하고 최솟값을 찾으려고 했다. 하지만 시간초과가 발생하는 것을 확인했다.

 

해당 문제는 알고리즘 고득점 Kit에 있는 문제이기 때문에 카테고리가 깊이/너비 우선 탐색이라는 것을 알고 있었지만, 마땅히 풀이 방식이 떠오르지 않아서 구글링을 통해 풀이 과정을 참고했다.

 

이 문제는 BFS를 통해 풀이할 수 있는 문제이다. BFS로 풀이할 수 있는 이유를 아래 사진을 통해 알아보자.

위는 입출력 예로 제시된 값들에 대해 그래프처럼 나열한 것이다.

• begin: "hit"
• target: "cog"
• words: ["hot", "dot", "dog", "lot", "log", "cog"]

나열할 때는 알파벳이 한 개 차이나는 경우만 나열을 했으며, 초록색으로 써진 글씨는 begin에서 부터 몇 번 바뀌었는지를 나타내는 횟수이다.

 

begin에서 시작해서 words에 현재 단어(w)와 알파벳 한 개만 차이나는 것들을 찾고, 만약 방문하지 않은 상태면 Que에 추가하고, 방문한 상태면 Skip하면 된다.

 

예를들면,

• 위 이미지와 같이 hit에서 시작할 때, words에서 알파벳 한 개 차이나는 단어를 찾으면 hot이 있다. hot은 이전에 방문한 적 없으므로 Que에 추가하면 된다. (계속 탐색하겠다는 뜻)
• dot에서 알파벳이 한 개 차이나는 경우를 나열하면, hot, lot, dog 등이 있다. 하지만 위 그림에서 살펴보면 hot과, lot은 이미 이전 Step(초록색 글씨) 방문한 값들이다. (visited가 True인 상태). 따라서 Que에 추가하지 않고 넘어간다.

 

1️⃣ Python 풀이

위 방법을 통해 풀이한 전체 코드는 아래와 같다.

from collections import deque

def solution(begin, target, words):
    answer = 0
    
    q = deque([begin])
    visit = {begin:0} # "{hit:0}"와 같은 형태로, {단어:바뀐 횟수}로 저장.
    while q:
        now = q.popleft()
        for w in words: # 모든 단어에 대해
            if w not in visit and compare(now, w): # 방문하지 않고, 1개 글자만 차이나는 경우
                q.append(w)
                visit[w] = visit[now] + 1
    
    if target in visit:
        return visit[target]
        
    return 0

def compare(s1, s2): # 하나의 알파벳만 차이나는지 비교하는 함수
    comp = 0
    for i in range(len(s1)):
        if s1[i] != s2[i]: # 다른 경우
            comp += 1
            if comp == 2:
                return False
    return True

---

이 문제를 통해, BFS/DFS에서 자주 출제되는 미로 문제가 아닌 다른 유형의 BFS/DFS 문제가 있을 수 있음을 알 수 있었다.

다음에 비슷한 유형의 문제를 마주했을 때, 해당 풀이 방식을 바로 떠올리고 풀 수 있으면 좋겠다.