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

from collections import deque
def solution(begin, target, words):
    if target not in words: # 아예 target없는 경우 미리 리턴
        return 0
    q = deque([(begin, 0)])
    while q:
        x, cnt = q.popleft()
        if x == target:
            return cnt
        for i in range(len(words)):
            diff = 0
            word = words[i]
            for j in range(len(x)):
                if x[j] != word[j]:
                    diff += 1
            if diff == 1:
                q.append((word, cnt + 1))
    return 0

 

: 문자열 변환하면,

하나하나 새로 만들어주며 조건에 맞는지 체크를 하는 식으로 전개하면 된다.

: 반복하는 과정을 거치면서 보통 for문을 사용하면서,

개선 여지를 보고 BFS,DFS 적절히 녹일 수 있는지 체크 OR  자료구조 선택여부 고민하면 풀리더라..

 

3단계 문제들은 다른 분들 풀이가 진짜 다양해져서 신기하다.. 근데 왜 보고 살펴봐도 감탄만 남고 배워지는 느낌이 없는지..? : (     실력도 없으면서 아집이 있는건가..? 나도 모르게 익히고 있는건가..? 사고가 더더더더더 ! 더 !  유연해지면 좋겠다.

 

 

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)

 

: 다른 분 풀이인데, 내가 한 방향이랑 되게 달라서 공부했다.

: 위에서는 하나씩 돌면서 글자차이 개수를 세는 것과 다르게 글자 구성 시에 하나씩 뺀 글자를 change함수에서 동일여부 체크하는 방식

: 그리고 위에서 q를 기반으로 풀이한 것과 다르게 dfs로 계속 밀고 들어가는 방식