Koala - 10기/코딩테스트 준비 스터디

[Programmers/Python] 단어 변환

happy_life 2023. 3. 6. 13:33

정답코드

# 복습 횟수:0, 00:30:00, 복습필요X
from copy import deepcopy
answer = 10

def dfs(begin, target, words, cnt, visited: list):
    global answer
    # 탈출 조건
    if begin == target:
        answer = min(answer, cnt)
        return
    
    for i in range(len(words)):
        if visited[i] == 1: continue

        check = []
        for j in range(len(words[i])):
            if begin[j] != words[i][j]:
                check.append(j)
        
        if len(check) == 1:
            visited[i] = 1 # 방문처리

            tmp = deepcopy(begin)
            begin = deepcopy(words[i])

            dfs(begin, target, words, cnt + 1, visited)

            visited[i] = 0 # 초기화
            begin = tmp # 초기화
             
    return

def solution(begin, target, words):
    if target not in words:
        return 0
    
    visited = [0 for i in range(len(words))]
    dfs(begin, target, words, 0, visited)


    return answer

 

 

1. list를 옮기는 것이므로 deepcopy를 통해서 초기화해주었습니다. ( 이렇게 하지 않을 경우 call by reference라서 주소값을 참조하므로 계속 영향을 받음)

2. 프로그래머스 특성상 answer 을 맨 위에 두고 global로 전역변수로 바꾸어 문제를 해결하였습니다.