[Programmers] 단어 변환(Python) / DFS

프로그래머스 고득점 KIT > 코딩테스트 연습 > 깊이/너비 우선 탐색(DFS/BFS) > Level 3 단어 변환 문제이다.

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

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

DFS를 먼저 떠올렸고, 계속 생각만 하다가 결국 코드로 구현하지 못하고 다른 사람의 코드를 참고했다.

참고 링크 : khann.tistory.com/79

프로그래머스 단어 변환 풀이 (파이썬)

기본적인 Stack을 사용한 DFS 풀이법에서 한 개의 알파벳만 다르다는 조건(isDifferent 함수)을 추가해,

이를 만족할 시 스택에 넣어주며 진행하는 방식으로 풀었다.

• dfs함수에서 while문 내의 for문이 끝날 때 같은 depth의 단어들의 탐색이 끝난 것이므로 answer += 1을 해주었다.
• isDifferent 함수는 두 단어가 인자로 들어오면 두 단어의 다른 알파벳 갯수를 리턴해주었다.
• 나름의 최적화로 words의 길이, begin의 길이를 인자로 넘기면서 계속 len() 해주지 않았고, 다른 알파벳이 2개 이상이면 그냥 2를 리턴했다.

파이썬 코드는 다음과 같다.

 

# (시작 단어, 비교 단어, 단어의 길이)를 인자로 넣으면 두 단어의 다른 알파벳 갯수 리턴
def isDifferent(x, y, L):
    temp = 0
    for i in range(L):
        if y[i] != x[i]:
            temp += 1
            if temp > 1:    # 2개 이상 다르면 그냥 2 리턴
                return 2
    return 1

def dfs(begin, target, words, check, N, L):
    global answer
    stack = [begin]
    while stack:
        x = stack.pop()
        if x == target:     # 타겟 단어 만나면 depth 리턴
            return answer

        for next in range(N):
            # 조건 1. 한 개의 알파벳만 다른 경우
            y = words[next]
            if isDifferent(x, y, L) == 1:
                if check[next]:
                    continue
                check[next] = 1
                stack.append(y)
        answer += 1    # depth 개념

def solution(begin, target, words):
    global answer
    # 조건 2. words에 있는 단어로만 변환 가능
    if target not in words:
        return 0
    answer = 0
    N = len(words)
    L = len(begin)
    check = [0] * N
    dfs(begin, target, words, check, N, L)
    return answer

 

* 고찰 : 기본적인 DFS 함수 뼈대는 그대로 사용한다. 코드를 외우는 방식보다 함수의 구조를 익혀 실제 코딩테스트에서 코드의 틀을 짤 때 활용하도록 하자. 각 기능을 하는 부분은 함수로 빼서 헷갈리지 않도록 하자. 쫄지 말고 덤벼서 진짜 구현력을 키우자!