[BFS] 단어 변환 (python) - 프로그래머스

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

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

 

BFS 문제인데, '단어 하나만 다를 경우 = 연결된 간선이 존재한다'로 해석해서 풀면 된다!

 

기본 BFS 로직이 아래와 같다면, 여기서 '3번 이 노드에서 연결된 다른 노드들' 과정이 복잡한 문제로 볼 수 있다.

# 1. 초기화
q = deque([start])

# 2. q가 빌 때까지 반복
while q:
	now = q.popleft()

	# 3. 이 노드에서 연결된 다른 노드들
	for 다음 노드 in 연결된 노드들:

		 # 4. 조건 만족시 일단 다 큐에 넣기
		if 문제 조건:
			q.append(now)

 

연결된 노드들을 체크해주는 함수 check를 만들어주고,

한번 방문했던 노드들은 다시 방문하지 않도록 visited 배열을 활용해서 체크해준다!

그 외에는 기본 BFS 풀이와 같다.

 

 

# BFS
# 단어 하나가 다른 건 두 노드가 연결된 간선이 있는 것과 같음!
from collections import deque
def solution(begin, target, words):
    n = len(words)
    visited = [False] * n
    
    def check(origin, new):
        n = len(origin)
        cnt = n
        for i in range(n):
            if origin[i] != new[i]:
                cnt -= 1

        if cnt == n-1:
            return True
        else:
            return False
    
    def bfs():
        q = deque()
        q.append([begin, 0])
        while q:
            now, cnt = q.popleft()
            if now == target:
                print(cnt)
                break

            for new in words:
                if not visited[words.index(new)]:
                    if check(now, new):
                        q.append([new, cnt+1])

        return cnt
    
    if not (target in words):
        return 0
    else:
        answer = bfs()
    return answer