[Python] DFS/BFS : 프로그래머스 LV.3 단어 변환

문제 링크   

프로그래머스

 

문제 해설 

사고의 흐름 

• 최소 변환 단계를 찾으면 된다. 먼저 target 값이 주어진 words 안에 있는지 확인하고 없다면 바로 0을 return 하자
• 그리고 일반적인 bfs 풀이처럼 시작해 보자. 방문여부를 false로 세팅하고 시작하자.
• q에 시작 단어와 목표 단어를 넣어주자, 그리고 popleft로 꺼내오면서 q가 빌 때까지 반복하면서 answer를 업데이트해 주면 되겠다
• answer를 업데이트하려면, 단어들끼리 비교하고 방문하지 않은 단어가 현재의 단어와 1글자만 다른 단어이면 방문처리하고 +1해 주면 되겠다.

코드 설명 

for i, word in enumerate(words):
	if not visited[i] and sum(c1 != c2 for c1, c2 in zip(current, word)) == 1:
    		visited[i] = 1
    		q.append((word, answer+1))

•  if not visited[i] and sum(c1 != c2 for c1, c2 in zip(current, word)) == 1:
  current와 word라는 두 단어 간에 문자 단위로 비교를 한다. zip(current, word)는 두 단어의 각 문자에 대한 쌍을 생성하고, c1 != c2 for c1, c2 in zip(current, word)는 두 단어의 각 문자 쌍에 대해, c1과 c2가 다른 경우 True를 반환하고, 같은 경우 False를 반환한다. 이렇게 반환된 값들의 합을 구하면, 즉, 다른 문자 쌍의 개수를 세는 것이 된다. 따라서 sum(c1 != c2 for c1, c2 in zip(current, word))는 현재 단어 current와 word 사이의 다른 문자 쌍의 개수를 알 수 있다. 이 값이 1인 경우, 즉, 단어 간에 한 글자만 다른 경우에 해당하는 단어로 이동할 수 있게 한다. 이 조건을 만족하는 경우에만 해당 단어를 방문 표시하고 큐에 추가하게 되고, 이렇게 하면 한 번에 한 글자만 변경하여 단어를 최소 변환할 수 있는 경로를 찾게 된다.

전체 코드 

from collections import deque

def solution(begin, target, words):
    answer = 0
    
    # target이 words 리스트 안에 없는 경우, 0을 반환
    if target not in words:
        return answer
    
    else:
    	# words의 방문 여부를 저장하는 리스트. 방문했으면 1, 아니라면 0
        visited = [0] * len(words)
        
        q = deque()
        q.append((begin,answer))
        
        while q:
            current, answer = q.popleft()
            
            if current == target:
                return answer
            
            for i, word in enumerate(words):
            	# word를 방문하지 않았고, current와 다른 문자의 개수가 1개라면 -> current와 word의 두 단어 간에 문자 단위로 비교함.
                if not visited[i] and sum(c1 != c2 for c1, c2 in zip(current, word)) == 1:
                    # 해당 word 방문했음 표시하고 단어와 answer를 큐에 추가
                    visited[i] = 1
                    q.append((word, answer+1))