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

 

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

코딩테스트 연습 - 단어 변환

 

 

---

1. 초기 큐에는 시작 단어와 변환한 횟수가 들어간다.

 

2. 하나씩 pop하면서 만약 target일 경우 cnt를 반환

 

3. target이 아니라면 방문하지 않은 words를 돌면서  한글자만 다른 단어를 찾는다.

 

4. 이것을 큐에 넣고 방문했음을 표시한다. 

 

 

 

 

 

 

코드 : 

 

from collections import deque 
def solution(begin, target, words):
    answer = 0
    q = deque()
    q.append([begin,0]) # 0은 변화한 횟수
    vis = [0 for i in range(len(words))] # 단어의 사용 여부를 나타낸 배열 
    
    while q :
        word , cnt = q.popleft()
        if word == target : 
            answer = cnt 
            break
        for i in range(len(words)) : # 단어들을 돌면서
            tmp_cnt = 0
            if vis[i] == 0 :  # 이 단어를 안썼다면
                for j in range(len(word)) :
                    if word[j] != words[i][j] :
                        tmp_cnt+=1 
                if tmp_cnt == 1 : # 만약 한글자만 다르다면
                    q.append([words[i],cnt+1])
                    vis[i] = 1  # 해당 단어 사용!
            
    
    return answer # 변환할 수 없는 경우 0을 반환

 

 

큐에서 하나를 뺀다. 

 

단어들을 돌면서 그 단어를 안썼다면 방금 큐에서 뺀 단어와 한 글자만 다른지 확인한다.

그후 한 글자만 다른게 맞다면 사용했음을 vis에 알리고 큐에 넣는다. (cnt를 하나 증가시킨채로) 

 

 

 

 

 

변환한 횟수를 큐에 같이 넣는다!!!!!

 

 

 

 

복습하면서 만든 코드 (target으로 만들지 못할경우 미리 return ) :

from collections import deque 
def solution(begin, target, words):
    answer = 0
    vis = [0 for i in range(len(words))]
    q = deque()
    q.append([begin,0])
    
    if target not in words : return 0

    while q :
        cur,cnt = q.popleft()
        if cur == target : return cnt
        for i in range(len(words)) :
            if vis[i] == 0 :
                tmp = 0
                for j in range(len(words[i])) :
                    if cur[j] != words[i][j] :
                        tmp+=1 
                if tmp == 1 :
                    q.append([words[i], cnt+1 ])

만약 words에 target이 없으면 만들지 못하기 때문에 미리 return 하도록 만들었다. 

근데 여기서 vis를 딱히 안해도 된다. 

 

 

 

배운 점 :

 

1.  deque 의 생성시 인수를 주는 것과 append 하는 것과의 차이 

 

d = deque()

d.append([begin,0])

과 

 

d = deque([begin, 0])은 다르다.

덱을 만든 후 append하면 첫번째 줄 출력과 같이 묶여서 저장된다.

그러나

덱을 만들 때 인수로 넣어주면 묶인 것이 아니라 하나 하나의 요소로 저장된다. 

 

 

 

 

 

 

 

참고 블로그 : 

 

https://velog.io/@op032/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-%EB%8B%A8%EC%96%B4-%EB%B3%80%ED%99%98python

프로그래머스 단어 변환(python)

 

 

복습 : 

 

✅ 20220620

✅ 20220623

✅ 20220624

✅ 20220625

✅ 20220626

✅ 20220628

✅ 20220630

🐾 20220922 (거의 3개월만에 풀었는데 성공!ㅎㅎ)

🐾 20220924