[DFS] 단어 변환

코딩테스트 연습 - 단어 변환

def check_able_word(word1: str, word2: str):
    count = 0
    for i in range(len(word1)):
        if word1[i] != word2[i]:
            count += 1
        if count == 2:
            return False
    return True
 
def solution(begin, target, words):
    def dfs(cur_word, count, path):
        if cur_word == target:
            # print('도착 =', path, count)
            # arrive_flag = True
            flag[0] = True  # 배열 인덱스 접근으로 할당하면 외부 변수 값을 컨트롤 할 수 있다.
            result.append(count)
 
        for check_word in words:
            if check_able_word(cur_word, check_word) and check_word not in path:
                dfs(check_word, count + 1, path + [check_word])
 
    # arrive_flag = False # 파이썬 알고리즘 인터뷰 337p 재할당 오류
    result = []
    flag = [False]
    dfs(begin, 0, [begin])
    print(result)
 
    if not flag[0]:
        return 0
    else:
        return min(result)

---

DFS를 사용하여 풀었다. check_able_word()을 충족하는 단어가 없으면 False를 반환하기 때문에 재귀함수의 종료조건을 따로 구현하지 않았다. dfs()의 3번째 파라미터인 path를 통해 한번 사용한 단어들을 저장하기 때문에 한번 사용했던 단어를 만나면 다음 for문으로 넘어간다.

 

+

dfs()는 solution()의 중첩 함수이다. 중첩 함수는 바깥에서 선언한 부모 함수의 변수를 자유롭게 읽을 수 있다.

바깥에서 선언한 변수인 arrive_flag의 초기값은 False이고 target을 찾았을 경우 중첩 함수안에서 True로 변경하려 했다. 하지만 dfs안에서의 arrive_flag = True는 중첩 함수안에서만 사용되는 지역 변수이며 여기서 재할당된 값은 부모 함수에 있는 arrive_flag에 영향을 줄 수 없다.

이럴 경우 가변객체인 리스트(flag = [False])를 사용하여 변수를 조작하면 된다. 조작된 값은 부모함수에서도 그대로 적용된다.