해당 글은 프로그래머스 문제를 푼 내용입니다.
프로그래머스 - 단어 변환: 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 함수를 작성해주세요.
⇒ “최소” “BFS” “기존 방문했던 것을 재방문하는 재귀하면 비효율적”
제한사항
- 각 단어는 알파벳 소문자로만 이루어져 있습니다.
- 각 단어의 길이는 3 이상 10 이하이며 모든 단어의 길이는 같습니다.
- words에는 3개 이상 50개 이하의 단어가 있으며 중복되는 단어는 없습니다.
- begin과 target은 같지 않습니다.
- 변환할 수 없는 경우에는 0를 return 합니다. (먼저, 판단해주면 좋을 조건)
입출력 예
| begin | target | words | return |
| "hit" | "cog" | ["hot", "dot", "dog", "lot", "log", "cog"] | 4 |
| "hit" | "cog" | ["hot", "dot", "dog", "lot", "log"] | 0 |
입출력 예 설명
예제 #1문제에 나온 예와 같습니다.
예제 #2target인 "cog"는 words 안에 없기 때문에 변환할 수 없습니다.
참고하면 좋은 블로그 모음
그림 위주 설명 블로그
https://www.hamadevelop.me/algorithm-wordchange
https://softvanilla.github.io/programmers/programmers_단어_변환/
https://velog.io/@ckstn0778/단어-변환-1
위 블로그에서는 해당 문제를 그림을 예시로 설명합니다. 입출력 예시로 예를 들면, begin 단어가 hit일 때 hit에서 1글자를 바꾸면 같은 단어인 관계를 간선(edge)이 연결된 노드로 취급하여 그림을 그립니다.
| level 0 | level 1 | level 2 | level 3 | level 4 |
| begin | i를 o로 변환 | h를 d나 l로 변환 | t를 g로 변환 | target |
| hit → | hot → | dot → | dog → | cog |
| lot → | log → | cog |
해당 문제는 최소 거리를 구하는 문제이다 보니 대부분의 풀이가 BFS로 풀려있습니다. DFS도 불가능하진 않습니다.
DFS 풀이 블로그: https://velog.io/@euneun/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-%EB%8B%A8%EC%96%B4-%EB%B3%80%ED%99%98BFSDFS-C-v5lnyekn
해당 블로그에서는 DFS를 활용해서 터미널 노드인 맨 끝 노드까지 탐색하고, 백트래킹 과정을 통해 최소 거리를 구하는 알고리즘을 활용하고 있습니다. DFS로 푸는 과정이 궁금하신 분은 해당 블로그의 내용을 추천드립니다.
풀이 코드
참고 블로그: https://nyeongnyeong.tistory.com/66
해당 블로그의 풀이에서는 node인 단어들을 숫자로 매핑해서 그래프 딕셔너리로 만들지 않습니다. BFS에서 중요한 전제인 한번 방문한 노드를 재방문하지 않는다. => 즉, 최소 거리를 구하는 특징을 활용하기 위해 단어들의 방문여부를 확인하는 알고리즘을 구현합니다. 단어 그대로를 노드 취급하여 각 node 단어의 같은 문자 개수가 1개인지 확인하는 조건문을 통해 방문여부를 판단합니다.
def solution(begin, target, words):
answer = 0
stacks = [begin]
visit = [0]*len(words)
if target not in words:
return 0
# bfs
while stacks:
stack = stacks.pop()
if stack == target:
return answer
for i in range(len(words)):
if len([j for j in range(len(words[i])) if words[i][j] != stack[j]]) == 1:
if visit[i] != 0:
continue
visit[i] = 1
stacks.append(words[i])
answer += 1
return answer
if __name__ == '__main__':
begin = "hit"
target = "cog"
words = ["hot", "dot", "dog", "lot", "log", "cog"]
print(solution(begin, target, words))
실행 시간
| 테스트 1 〉 | 통과 (0.01ms, 10.3MB) |
| 테스트 2 〉 | 통과 (0.08ms, 10.2MB) |
| 테스트 3 〉 | 통과 (0.55ms, 10.3MB) |
| 테스트 4 〉 | 통과 (0.02ms, 10.3MB) |
| 테스트 5 〉 | 통과 (0.00ms, 10.2MB) |