[Python : 프로그래머스] 단어 변환

문제

https://programmers.co.kr/learn/courses/30/lessons/43163?language=python3

풀이

최초 시도

def DFS(compw, words, count):
    for w in range(len(words)):
        if len([d for d in range(len(word)) if words[d] != compw[d]]) == 1:
            return DFS(words.pop(w), words, count+1)

    return count
    
def solution(begin, target, words):
    if target not in words :
        return 0
    else :
        return DFS(begin, words, 0)

Stack은 탐색 과정에 “성공한 것들을 모아서 다음 후보로 만들어 둔 리스트”다.
그런데 “전체 탐색해야할 목록” 으로 이뤄진 리스트로 착각하고 문제에 접근했다.
그러니 문제가 풀릴리가 없다.

심지어 DFS 함수를 return으로 종료시켜버리니
for문의 인덱스 에러가 발생한다.
처음부터 다시 해보자.

def DFS(begin, target, words, visit, count):
    stack = [begin]
    while stack :
        spword = stack.pop()
        if spword == target :
            return count
        
        for word in words :
            if len([d for d in range(len(word)) if word[d] != spword[d]]) == 1:
                if visit[word] == 0:
                    visit[word] = 1
                    stack.append(word)

        count += 1
                
def solution(begin, target, words):
    visit = {w:0 for w in words}
    return DFS(begin, target, words, visit, 0) if target in words else 0

첫 코드에서 스택을 사용하기 때문에 방문기록을 알아볼 필요가 없었지만,
이번 코드에선 스택을 탐색 성공 리스트로 사용하기 떄문에 필수다.
방문 기록을 확인하지 않으면 스택에 끝없이 값이 들어가 무한루프에 빠지게 된다.

더 나은 풀이

answer = 0
def solution(begin, target, words):

    dfs(begin, target, 0, words)
    return answer

def change(fr, to):
    for i in range(len(fr)):
        if fr[:i]+fr[i+1:] == to[:i]+to[i+1:]:
            return True
    return False

def dfs(begin, target, d, words):
    global answer
    # print(begin)
    # print(words)
    if begin == target:
        # print(d)
        answer = d
        return
    else:
        if len(words) == 0:
            return 
        for w in range(len(words)):
            if change(begin, words[w]):
                word = words[:w]+words[w+1:]
                dfs(words[w], target, d+1, word)

알고리즘보다는 다른게 눈에 띄어서 구경했던 코드.
전역 변수를 저렇게 사용하던데, 개인적으로
“전역변수는 최소화 하는 것이 좋다.” 라는 고상한 고정관념을 가지고 있다.

전역변수는 사용법에 대해서만 기억해두고…
다른 언어들과 다르게 파이썬은 함수를 위쪽에 먼저 선언할 필요가 없나보다.
호출 당하는 함수가 아래쪽에 있는게 신기했다.

더 열심히 공부하자.