프로그래머스: 단어변환 (python, 파이썬 )

1. 문제

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

 

2. 풀이

BFS

 

3. 구현

1. dictionary에 append할 때

if item1 in dic:
    dic[item1].append(item2)
else:
    dic[item1]=[item2]

2. AttributeError: 'str' object has no attribute 'append'

if item1 in dic:
    dic[item1].append(item2)
else:
    dic[item1]=item2
4와 같이 쓰면 dictionary가 key:str, value:str로 연결되서 dict[item1]에 str를 반환해 나는 에러


if item1 in dic:
    dic[item1].append(item2)
else:
    dic[item1]=[item2]
로 바꾼다

3. item1 과 item2가 1글자 차이나는 경우, sum([])으로 리스트형태로 만들어줘야 sum 이 작동한다.

if sum([w1!=w2 for w1, w2 in zip(item1, item2)])==1:

4. 원하는 사이즈로 빈리스트 만들때

visit = [0 for i in range(52)]

5. queue 사용할 때

from collections import deque

q = deque()
cur = q.popleft()

 

전체 구현

from collections import deque
def solution(begin, target, words):
    answer = 0
    dic = {}
    
    words.append(begin)
    if target not in words:
        return 0
    words.append(target)
    
    for item1 in words:
        for item2 in words:
            if sum([w1!=w2 for w1, w2 in zip(item1, item2)])==1:
                if item1 in dic:
                    dic[item1].append(item2)
                else:
                    dic[item1] = [item2]
    
    visit={}
    q = deque()
    q.append((begin, answer))
    visit[begin]=True
    
    while q:
        cur = q.popleft()
        for iter in dic[cur[0]]:
            if iter in visit:
                continue
            else:
                if iter == target:
                    return cur[1]+1
                else:
                    q.append((iter, cur[1]+1))
                    visit[iter]=True
    
    return answer