[프로그래머스] 단어 변환 (Lv 3)

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

프로그래머스

 

앞에서 푼 문제와 유사하나, 이번에는 그래프가 꽁으로 주어져 있지 않아 직접 만들어야 한다.
방문 여부만 체크하면 되므로, 이번에는 굳이 거리를 다 저장할 필요는 없다.!

 

from collections import deque
def bfs(start, end, vertex, visited):
    # 시작지점의 거리는 0
    visited[start] = True
    queue = deque()
    queue.append((start, 0))
    
    while queue:
        cur_v, dist = queue.popleft()
        # 다음 꼭지점 목록을 모두 가져오고 순차대로 돌린다.
        next_v = vertex[cur_v]
        for nv in next_v:
            if nv == end:
                # 다음 거리는 +1
                return dist + 1
            elif not visited[nv]:
                # 방문한적이 없으면, 점과 거리를 넣는다.
                visited[nv] = True
                queue.append((nv, dist+1))
    return 0
    

def check_word(x, y):
    cnt = 0
    for i in range(len(x)):
        if x[i]==y[i]:
            cnt += 1
    if cnt == len(x)-1:
        return True
    else: 
        return False
    
def solution(begin, target, words):
    # 방문 목록과 꼭지점 목록을 만든다.
    # 방문 거리는 거리만 담을거라 1차원 배열, 꼭지점 목록은 2차원으로 해서 연결성을 담는다.
    visited = [False] * (len(words) + 1)
    vertex = [[] for _ in range(len(words) + 1)]
    
    # 맨 처음 시작점도 넣어서, 그래프 정점으로 연결 시킬 생각.
    words.insert(0, begin)
    # 애초에 빠른 탈락조건
    if target not in words:
        return 0
    
    for i in range(len(words)):
        for j in range(len(words)):
            if check_word(words[i], words[j]):
                vertex[i].append(j)
    start = 0
    end = words.index(target)
    answer = bfs(start, end, vertex, visited)
    return answer