[깊이/너비 우선 탐색 (DFS/BFS)] 프로그래머스 - 단어 변환

문제 출처 : https://programmers.co.kr/learn/courses/30/lessons/43163

 

문제 설명 : 

두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다.

1. 한 번에 한 개의 알파벳만 바꿀 수 있습니다. 2. words에 있는 단어로만 변환할 수 있습니다.

예를 들어 begin이 "hit", target가 "cog", words가 ["hot","dot","dog","lot","log","cog"]라면 "hit" -> "hot" -> "dot" -> "dog" -> "cog"와 같이 4단계를 거쳐 변환할 수 있습니다.

두 개의 단어 begin, target과 단어의 집합 words가 매개변수로 주어질 때, 최소 몇 단계의 과정을 거쳐 begin을 target으로 변환할 수 있는지 return 하도록 solution 함수를 작성해주세요.

제한사항

• 각 단어는 알파벳 소문자로만 이루어져 있습니다.
• 각 단어의 길이는 3 이상 10 이하이며 모든 단어의 길이는 같습니다.
• words에는 3개 이상 50개 이하의 단어가 있으며 중복되는 단어는 없습니다.
• begin과 target은 같지 않습니다.
• 변환할 수 없는 경우에는 0를 return 합니다.

입출력 예

begintargetwordsreturn

begin	target	words	return
"hit"	"cog"	["hot", "dot", "dog", "lot", "log", "cog"]	4
"hit"	"cog"	["hot", "dot", "dog", "lot", "log"]	0

 

문제 풀이 : 

전형적인 bfs 문제였다. 이 문제는 bfs를 이용해서 해결 할 수 있는지, 그리고 그래프 자료 구조로 만들 수 있는지 정도를 파악하는 것 같다. 물론 오랜만에 그래프로 만들고 bfs를 구현해보느라 조금 시간은 걸렸다. 

 

from collections import deque

def bfs(edge, visited, target, words):
    queue = deque([[0, 0]]) #앞의 수가 노드 번호, 뒤의 수는 count
    visited[0] = True
    answer = 0
    while queue:
        v = queue.popleft()
        print
        if words[v[0]] == target:
            answer = v[1]
            break
        for i in edge[v[0]]:
            if not visited[i]:
                visited[i] = True
                queue.append([i, v[1]+1])
    return answer
    
def solution(begin, target, words):
    words.insert(0, begin)    
    n = len(words)
    l = len(begin)
    edge = [[] for _ in range(n)]
    for i in range(n):
        for j in range(n):
            count = 0
            if i == j: 
                break
            for k in range(l):
                if words[i][k] == words[j][k]:
                    count += 1
            if count == l - 1:
                edge[i].append(j)
                edge[j].append(i)
    visited = [False] * n
    return bfs(edge, visited, target, words)

먼저 words리스트에 begin 단어는 주어지지 않아서 begin을 0번째에 추가해 주었다. (target의 경우는 words 리스트 안에 없으면 단어 변환이 안되는 경우로 0을 리턴해줘야 하기 떄문에 추가하지 않는다) 그리고 단어를 두 개씩 비교하면서 각 단어들이 한 글자만 빼고 동일한 철자를 가지면 엣지가 연결되어 있음을 인접 리스트로 표현해줬다. 이렇게 완성된 그래프를 가지고 bfs 너비우선탐색을 진행했다. 하나의 경로부터 깊게 파는 깊이우선탐색보다는 빠를 것 같아서 한 단계씩 확인하는 너비우선탐색을 사용했다. 시작점인 0번째부터 출발해서 0번째 노드와 연결된 다른 노드들을 방문하고 스택에 넣는다. 그 다음엔 스택에서 노드를 하나 빼서 그 다음 단계의 노드를 방문처리하고 스택에 넣는다. 이 과정을 target 단어를 만날 때까지 한다. 처음엔 words의 마지막 인덱스에 도달하면 찾은 것이라고 생각했는데, 앞서 말한 것처럼 target이 words 리스트 안에 아예 존재하지 않는 경우를 구분해내기 어려워서 target 단어 역시도 bfs 함수의 파라미터로 넘겨 주었다. 

 

어려운 문제는 아니었지만 bfs를 정확하게 알고 있어야 쉽게 풀 수 있는 문제였다! 이런 문제 몇 개 더 풀어보면 까먹지 않고 기억할 수 있을 것 같다.