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

🔫 문제 : 단어 변환

📍 정리

현재 단어와 words에 있는 단어가 알파벳 하나만 다르다면 words에 있는 단어로 변경해주면 된다.

- words에 target이 없다면 최종 목표인 target으로 바꿀 수 없으므로 0을 반환한다.

 

 

🌱 풀이 방법

어느 경우를 탐색해도 깊이가 같다 -> BFS를 사용하자!

 

1️⃣ 현재 단어와 변환 횟수를 담을 queue와 방문 여부를 확인할 list를 만들어준다.

q = deque()
q.append([begin, 0])

visit = [0] * len(words)

2️⃣ words에 target이 존재하는지 확인

if target not in words:
	return 0

3️⃣ queue에서 현재 단어와 변환 횟수를 꺼낸 후, target과 현재 단어가 같은지 확인한다. 

word, cnt = q.popleft()
      
if target == word:
	return cnt

4️⃣ 단어가 다르다면, 알파벳 몇개가 다른지 계산해서 1개가 다르다면 해당 단어에 방문 표시 + 해당 단어로 변경 + 변환 횟수 1 증가를 해준다.

for i in range(len(words)):
            different_cnt = 0
            
            if not visit[i]: # 방문 여부 확인 
                
                # 알파벳 몇개가 다른 지 찾기
                for j in range(len(word)):
                    if word[j] != words[i][j]:
                        different_cnt += 1
                        
                # 알파벳 1개가 다르다면 단어 바꾸기        
                if different_cnt == 1:
                    visit[i] = 1
                    q.append([words[i], cnt+1])

 

 

👩🏻‍💻 전체 코드

from collections import deque

def solution(begin, target, words):
    q = deque()
    q.append([begin, 0])
    
    visit = [0] * len(words)
    
    # words에 target이 존재하지 않는다면 변환을 할 수 없음
    if target not in words:
        return 0
    
    while q:
        word, cnt = q.popleft()
        
        if target == word:
            return cnt
        
        for i in range(len(words)):
            different_cnt = 0
            
            if not visit[i]: # 방문 여부 확인 
                
                # 알파벳 몇개가 다른 지 찾기
                for j in range(len(word)):
                    if word[j] != words[i][j]:
                        different_cnt += 1
                        
                # 알파벳 1개가 다르다면 단어 바꾸기        
                if different_cnt == 1:
                    visit[i] = 1
                    q.append([words[i], cnt+1])
                    
    return 0

 

 

 

 

🫧 결과