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

문제 설명

두 개의 단어 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 합니다.

입출력 예

입출력 예

입출력 예 설명

예제 #1
문제에 나온 예와 같습니다.

예제 #2
target인 "cog"는 words 안에 없기 때문에 변환할 수 없습니다.

---

나의 풀이

BFS/DFS를 사용해야 한다는 아이디어와 주어진 words를 인접 리스트로 변환해야 한다는 아이디어는 어렵지 않게 떠올렸지만 BFS를 구현하는 것이 아직은 미숙하여 시간이 오래 걸린 문제이다. (거리를 계산하는 부분에서 오래 걸렸다)

아이디어

• words의 각 단어들의 한 문자 차이나는 단어들을 모두 찾는다.
  • 예를 들어 words로 ["hot", "dot", "dog", "lot", "log"] 가 주어졌을 때 "hot" 과 한 문자 차이나는 단어들은 ["dot", "lot"] 이 있다. 이런 식으로 모든 단어에 대해 한 문자 차이나는 단어들을 찾아 인접 리스트의 형태로 만든다.
  • 인접 리스트를 만들 때 노드가 정수가 아니므로 dict로 만들었다.
• 앞서 만들어진 인접 리스트를 가지고 target의 단어가 나올 때까지 BFS로 탐색한다. 즉 최단 거리를 구하는 것인데 최단 거리를 구하는 문제에서는 DFS보다 BFS가 효과적이다. (DFS의 경우 모든 경로를 다 탐색해야하지만 BFS의 경우 목표가 발견되면 바로 종료할 수 있다)

# BFS

from collections import deque

def bfs(graph, begin, target, visited):
    distance = {begin:0}
    queue = deque([begin])
    visited[begin]= True
    while queue:
        word = queue.popleft()
        for key in graph[word]:
            if target in graph[word]: key = target
            if not visited[key]:
                visited[key] = True
                queue.append(key)
                distance[key] = distance[word] + 1
                if key == target: return distance[key]
    return 0

BFS에서는 최단 거리를 구하기 위해 distance 라는 dict를 선언하였다.

나머지 부분은 BFS의 기본적인 형태와 동일하고, while문 내부의 for문 내부에서 distance[word] + 1은 부모 노드까지의 길이 + 1을 의미한다.

변환할 수 없는 경우 0을 return한다는 제한사항이 있었으므로 마지막 부분에 return 0이 존재한다.

# solution 함수

def solution(begin, target, words):
    wordDiff = lambda w1, w2 : sum([True for i in range(len(w1)) if w1[i] != w2[i]]) # 다른 문자 개수
    graph = {word : [w for w in words if wordDiff(word, w)==1] for word in words+[begin]} # 하나 다른 문자들
    visited = {words[i] : False for i in range(len(words))} # 방문 테이블
    return bfs(graph, begin, target, visited)

wordDiff는 매개 변수로 받은 두 단어(길이가 같다고 가정)에서 같은 위치의 다른 문자가 몇 개 인지 return 하는 함수이다.

graph에서는 위에서 설명한 인접 리스트를 만드는데 맨 뒤의 words+[begin]에서 시작 지점을 words에 넣어준다. 그래야 BFS로 탐색할 수 있기 때문.

이후 각 단어 word를 순회하는데 word는 키가 된다.

그리고 words에서 각 단어 w를 순회하여 word와 w의 문자 차이가 1개가 나는 단어들을 리스트로 만들어 값으로 사용한다.

이렇게 만들어진 인접 리스트(graph), 시작점(begin), 타겟(target), 방문 테이블(visited)를 BFS의 매개 변수로 넣어준다.

 

전체 소스코드

from collections import deque

def bfs(graph, begin, target, visited):
    distance = {begin:0}
    queue = deque([begin])
    visited[begin]= True
    while queue:
        word = queue.popleft()
        for key in graph[word]:
            if not visited[key]:
                visited[key] = True
                queue.append(key)
                distance[key] = distance[word] + 1
                if key == target: return distance[key]
    return 0

def solution(begin, target, words):
    wordDiff = lambda w1, w2 : sum([True for i in range(len(w1)) if w1[i] != w2[i]]) # 다른 문자 개수
    graph = {word : [w for w in words if wordDiff(word, w)==1] for word in words+[begin]} # 하나 다른 문자들
    visited = {words[i] : False for i in range(len(words))} # 방문 테이블
    return bfs(graph, begin, target, visited)

 

테스트 결과