DFS/BFS - 단어 변환

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

호기롭게 BFS로 접근하였지만 흠.. 일단 의식의 흐름대로 한번 써봤다

from collections import deque

def bfs(graph, words, begin, ct, target):
    count, c, i = 0, 0, 0
    queue = deque([words[i]]) # ["hot"]
    answer = []
    v = queue.popleft()
    while True:
        for w in v:
            if w in begin:
                count+=1
        if count == (ct-1):
            begin = v
            answer.append(begin)
        
        if len(set(target) - set(begin)) == 1:
            answer.append(target)
            break
        
        count = 0
        i += 1
        if i == len(words):
            break
        queue.append(words[i])
        v = queue.popleft()
    return len(answer)
            
def solution(begin, target, words):
    if not target in words:
        return 0
    visited = [False]*len(words)
    answer = bfs(words, words, begin, len(begin), target)
    return answer

만약 target과의 문자 차이가 1개일 경우, (그리고 target의 단어가 words안에 있으면) 바로 while문을 나가기. +1 만 해주면 과정은 차피 끝이니까 ㅇㅇ...
제출해보니 의외로 선방하긴했다..^^

의외로 시간초과가 안떴다. 그러면 내가 테스트케이스 무언가를 지금 고려 안했다는 것같은데..
구글링을 해보니까 내가 words의 순서가 고정되어있다고 생각했던 것이 문제였다 그럼 이거 다 갈아엎어야 하나..? ㅎ
아님 그냥 리버스한걸 뒤에 하나 더 붙여서 해볼까 싶었다.

from collections import deque

def bfs(graph, words, begin, ct, target):
    count, c, i = 0, 0, 0
    queue = deque([words[i]]) # ["hot"]
    answer = []
    v = queue.popleft()
    while True:
        if len(set(begin) - set(v)) == 1:
            begin = v
            answer.append(begin)        
        elif begin == target:
            break
        
        if len(set(target) - set(begin)) == 1:
            answer.append(target)
            break

        count = 0
        i += 1
        if i == len(words):
            break
        queue.append(words[i])
        v = queue.popleft()
    return len(answer)
            
def solution(begin, target, words):
    if not target in words:
        return 0
    words += words[::-1]
    answer = bfs(words * len(words), words, begin, len(begin) * 2, target)
    
    return answer

응 안돼~ 돌아가..
일단 set으로 비교하는 게 틀렸음
함수를 하나 더 만들어서 비교를 했고
하나의 자리에서만 차이가 나는거니까 인덱스도 확인해줬어야함

from collections import deque

def find(target, begin):
    count = 0
    for i in range(len(begin)):
        if begin[i] == target[i]:  
            count+=1
    return count

def bfs(words, begin, target):
    
    count= 0
    obj = len(begin)-1
    
    queue = deque(words) # ["hot", "dot", "dog", "lot", "log", "cog"]
    goal = target[:]
    answer = []
    v = queue.popleft()

    while queue:
        # 현재 단어랑 바꿀 단어랑 알파벳 비교
        # 만약 1개밖에 차이가 안나면 걔로 바꿈

        print("현재", begin, v, find(begin, v), obj)
        if v == target and find(begin,v) == obj:
            count += 1
            return count
        
        if find(begin, v) == obj:
            begin = v
            count += 1 # 바꾼 횟수
            # 근데 만약 바꾼 begin이랑 target이 차이가 1개 밖에 안나면
            # 한번만 더 바꾸면 되니까 끝내기
            if find(target, begin) == obj:
                count += 1
                return count
        else: 
            queue.append(v)
        v = queue.popleft()
    return count
            
def solution(begin, target, words):
    if not target in words:
        return 0
    answer = bfs(words, begin, target)
    return answer