[프로그래머스 lv3] 단어 변환 (bfs/파이썬) 2/3

https://school.programmers.co.kr/learn/courses/30/lessons/43163

Try 1

from collections import deque

answer = 0

def changable(now, target):
    cnt = 0
    for c in now:
        if c in target: cnt+=1
    if cnt == len(target)-1: return True
    return False

def bfs(now, target, words):
    q = deque()
    q.append((now, 0))
    while q:
        n, d = q.popleft()
        for word in words:
            if changable(n, word):
                if word == target: return d+1
                words.remove(word)
                q.append((word, d+1))
    return 0


def solution(begin, target, words):
    global answer
    if target not in words: return 0
    for word in words:
        if changable(begin, word):
            answer = bfs(begin, target, words)
    return answer

Try2

changable을 수정한 코드. 전부 정답으로 떴다.

from collections import deque

answer = 10001

def changable(now, target):
    diff = 0
    for i in range(len(now)):
        if now[i] != target[i]: diff+=1
    if diff == 1: return True
    return False

def bfs(now, target, words):
    q = deque()
    q.append((now, 0))
    while q:
        n, d = q.popleft()
        for word in words:
            if changable(n, word):
                if word == target: return d+1
                words.remove(word)
                q.append((word, d+1))
    return 0


def solution(begin, target, words):
    global answer
    if target not in words: return 0
    for word in words:
        if changable(begin, word):
            answer = min(bfs(begin, target, words), answer)
    if answer == 10001: answer = 0
    return answer

그런데 이게 어떻게 가능한거지?
당장 이렇게만 돌려봐도 틀린 답이 나온다.
프로그래머스는 테스트 케이스가 부족한 거 같다.

첨부한 사진의 경우, 가장 짧게 변환하는 방법은
hit -> hot -> lot -> log -> cog
로 총 4단계다.
그런데 내 코드를 실행할 시 hot -> dot -> lot -> log -> cog 처럼 불필요한 과정을 거치게 된다.

일단 remove를 통해서 사용한 단어는 지워주는 선택이 합리적이긴 하다. (백트래킹)
즉 hot에서 dot, lot 두 수로 변환할 수 있을 시 lot으로 바로 가는 과정이 필요한데 어딘가에서 문제가 생긴 것이다.

Try3. 정답 코드

from collections import deque

answer = 10001

def changable(now, target):
    diff = 0
    for i in range(len(now)):
        if now[i] != target[i]: diff+=1
    if diff == 1: return True
    return False

def bfs(now, target, words):
    q = deque()
    q.append((now, 0))
    while q:
        n, d = q.popleft()
        for word in words:
            print("d:", d, word)
            if changable(n, word):
                if word == target: return d+1
                # words.remove(word)
                q.append((word, d+1))
    return 0


def solution(begin, target, words):
    global answer
    if target not in words: return 0
    for word in words:
        if changable(begin, word):
            answer = min(bfs(begin, target, words), answer)
    if answer == 10001: answer = 0
    print(answer)
    return answer

solution("hit", "cog", ["hot", "zit", "dot", "lot", "log", "cog"])

문제를 알았다.
words.remove(word) 파트로 인해 solution 내 changable이 한 번만 실행되는 문제가 있었다. (예시를 돌릴시 chanable 함수가 두 번 실행되어야 함)

따라서 그냥 bfs로 백트래킹 신경 안 쓰고 이렇게 푸는게 맞다.

다만 정확성은 올라갔고, 버그가 없는 코드도 맞으나 테스트 3의 소요 시간이 대단히 오래 걸리기 시작한다.
따라서 visit을 실행해주는게 맞지 않나.. 하고 생각 중