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

링크: https://school.programmers.co.kr/learn/courses/30/lessons/43163?language=python3 

프로그래머스

아이디어

• words에 target단어가 없는 경우 0 반환
• 첫 bfs를 시작할 시작 노드 찾기( begin에서 갈 수 있는 문자들)
• for문을 이용해 1번 조건을 만족하는 단어를 찾음
• 위와 같은 방식으로 그래프를 만들어 BFS를 진행
• 방문처리를 깊이 표현과 동시에 진행
• target노드가 나오면 현재 노드의 깊이 출력

자료구조

• Queue(BFS)
• 방문: int []

코드구현

from collections import deque


def solution(begin, target, words):
    w_len = len(begin)
    w_cnt = len(words)
    cnt = [0]*(len(words))
    # words에 target이 없으면 0반환
    if target not in words:
        return 0
    q = deque([])

    # BFS 시작 점을 미리 큐에 넣기
    for i in range(w_cnt):
        tmp = 0
        for j in range(w_len):
            if begin[j] != words[i][j]:
                tmp += 1
        if tmp == 1:
            q.append(i)
            cnt[i] += 1
    #BFS 시작
    while q:
        now = q.popleft()
        if words[now] == target:
            return(cnt[now])
        else:
            for i in range(w_cnt):
                if cnt[i] == 0:
                    tmp = 0
                    for j in range(w_len):
                        if words[now][j] != words[i][j]:
                            tmp += 1
                    if tmp == 1:
                        q.append(i)
                        cnt[i] = cnt[now] +1
                
    return 0

마무리

• 이젠 진짜 BFS가 쉽다고 느껴지기 시작함
• 방문처리와 깊이 표현이 동시에 이뤄지는 유형의 문제들이 많다 인지해두자
• 다음 문제부터는 DFS를 시작해보려 한다.