[programmers] 43163. 단어변환

문제

43163. 단어변환

분석

Constraints
1. 한 번에 한 개의 알파벳만 바꿀 수 있습니다.
2. words에 있는 단어로만 변환할 수 있습니다.

• 해당 제약 조건으로부터 한 글자만 다른 단어 = 연결되어있는 노드로 생각하여 연결그래프를 먼저 만들어놓고 시작했다.

• 다른 DFS/BFS 문제와 다르게 그래프를 만들어주는 작업을 직접 해주어야 하기 때문에 더 처음에 풀기가 어려울 수 있다는 생각이 듦

첫 코드 작성 - DFS

def solution(begin, target, words):
    # 만약 words에 없으면 확인 안해도 됌
    if target not in words:
        return 0
    
    # lets make a graph!
    all_words = [begin] + words
    all_words_n = len(all_words)

    graph = {k:[0]*(all_words_n) for k in range(all_words_n)}
    visited = [False] * all_words_n
    # 1. graph 만들기
    for w_idx, w in enumerate(all_words):
        for comp_idx in range(all_words_n):
            count=0
            # 같은 단어이면 graph는 연결 X
            if w == all_words[comp_idx]:
                continue
            for s_idx in range(len(w)):
                if w[s_idx] != all_words[comp_idx][s_idx]: # char가 다르면
                    count+=1
                if count > 1: # graph가 연결되어있지 않다고 판단
                    break
            if count==1:
                graph[w_idx][comp_idx] = 1  # graph가 연결되어있지 않다고 판단
    global min_result
    
    min_result = -1
    # 2. DFS 시작
    def dfs(cur_word, cur_idx, depth):
        global min_result
        visited[cur_idx] = True

        # target 과 같아졌을 때 멈춰야함
        if cur_word == target:
            if min_result > depth or min_result==-1:
                min_result = depth
            return
        
        for next_idx, next_v in enumerate(graph[cur_idx]):
            if not visited[next_idx] and next_v == 1:
                dfs(all_words[next_idx], next_idx, depth+1)
                # 이거 해줘야!
                visited[next_idx] = False
        
    dfs(begin, 0, 0)
    return min_result

처음 시행착오

• DFS를 진행하면, 최단거리가 아니더라도 순회하는 순서에 따라 종료될 수 있다. 이는 visited가 이미 된 노드는 다시 방문하지 않기 때문이다. 따라서, 중요한 점은 dfs() 함수가 return 되면 해당 노드의 visited 다시 reset시켜주어야 한다.

ex) 그래프를 어떻게 순회하냐에 따라
hot -> dot -> dog -> log -> cog 순으로 먼저 순회하면 바로 length = 5로 종료!
하지만 hot -> dot -> dog -> cog의 최단거리가 존재!

• 해당 부분의 코드는 아래와 같다.

        for next_idx, next_v in enumerate(graph[cur_idx]):
            if not visited[next_idx] and next_v == 1:
                dfs(all_words[next_idx], next_idx, depth+1)
                ############ HERE ############ 
                visited[next_idx] = False
                ##############################

2번째 코드 - BFS

• 최단 거리를 찾을 때에는 DFS로 풀면 Time Limit에 걸릴 수 있다..
• 따라서 BFS로 코드를 구현해보았다.
• memory도 더 적게 쓰기 위해서 graph를 만들 때, 해당 연결 노드만을 append해주는 graph로 바꾸어보았다.

from collections import deque
def solution(begin, target, words):
    # 만약 words에 없으면 확인 안해도 됌
    if target not in words:
        return 0

    
    # 1. lets make a graph!
    all_words = [begin] + words
    all_words_n = len(all_words)
    word_graph = {k:[] for k in range(all_words_n)}
    
    visited = [False] * all_words_n
    queue = deque()
    min_result = -1
    
    def difference_check(orig_word, comp_word):
        count = 0
        # 같은 숫자면
        if orig_word == comp_word:
            return 0
        for i in range(len(orig_word)):
            if orig_word[i] != comp_word[i]:   # 다른 알파벳을 가지면
                count+=1
        # print("difference_check: ", orig_word, comp_word, count)
        return count

    for orig_i, orig_w in enumerate(all_words):
        for comp_i, comp_w in enumerate(all_words):
            if difference_check(orig_w, comp_w) == 1:
                word_graph[orig_i].append(comp_i)
    
    visited[0] = True
                # word_idx, depth 
    queue.append((0, 0))
    min_result = -1

	# 2. lets start BFS!
    while queue:
        cur_idx, cur_dep = queue.popleft()

        if all_words[cur_idx] == target:
            min_result = cur_dep
            break
        
        for next_idx in word_graph[cur_idx]:
            if not visited[next_idx]:
                visited[next_idx] = True
                queue.append((next_idx, cur_dep+1))
    
    return min_result

결과

if __name__ == "__main__":
    begin = "hit"
    target = "cog"
    words = ["hot", "dot", "dog", "lot", "log", "cog"]
    print(solution(begin, target, words))

4