문제
두 개의 단어 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 합니다.
문제를 보고 든 생각
일단 이 문제가 dfs나 bfs문제인가 싶었다.
한붓 그리기로 문제를 해결할 수 있으니 dfs인 것 같기는 한데
어떻게 하면 좋을지 확신이 서지 않았다.
가장 문제였던 건, 도대체 어떻게 한 글자만 차이나는 걸 탐색할 수 있을까였다.
문자열과 문자열을 비교할 때 한 글자만 차이나는 걸 감지할 수 있는 무언가가 있었나 계속 생각해봤다.
나의 아이디어
생각하면 생각할 수록 이 문제는 문자열과 문자열을 비교했을 때 한 글자만 차이나는 문자열이 무엇인지 탐색해내는 게 관건인 문제같았다.
사실 그냥 for문으로 돌리면 될 것 같았다. 문자열도 배열 안에 들어있는 요소들은 모두 길이가 같기도 하고, 문자열은 또 배열처럼 참조가 되니까.
하지만, 그렇게 하기가 싫었다.
분명 while문을 돌려야 풀 수 있는 문제라고 생각이 들었기 때문이었다. for문을 써버리면 O(n^2)의 시간복잡도를 갖게 되는 풀이가 돼버려서 그렇게 하기가 싫었다.
그러나 그 방법을 제외하면 도대체 어떻게 한 글자만 차이나는 문자열을 탐색할 수 있을지 도저히 떠오르지가 않았다.
그래서 결국 for문을 사용해서 두 문자열을 비교한 다음 다른 문자열이 발견될 때 count를 하나씩 올리는 것으로 했다.
그리고 그 문자열을 target 문자열과도 비교해서 target 문자열과 count 차이가 가장 적게 나는 것으로 다음 문자열을 알아서 고르도록 했다.
결과
def solution(begin, target, words):
visited = [False for _ in range(len(words))]
def str_matching(base, compare): # 현재 문자열과 words안의 문자열 비교
diff_count = 0 # 현재 문자열과 비교했을 때 몇 글자가 차이 나는지 저장한다.
for index, char in enumerate(base):
if char != compare[index]:
diff_count += 1
def compare_with_target(compare): # words안의 문자열과 target 문자열 비교
target_compare_count = 0 # words안의 문자열과 target을 비교했을 때 몇 글자가 차이나는지 저장한다.
for index, char in enumerate(compare):
if char != target[index]:
target_compare_count += 1
return target_compare_count
return diff_count, compare_with_target(compare)
reps = 0
while target in words: # words 안에 target이 없다면 들어오지 못하도록 한다.
min_count = 1e9
for index, word in enumerate(words):
diff_count, target_compare_count = str_matching(begin, word)
# 한 글자만 차이 나야 하기 때문에 diff_count는 항상 1이고 target_compare_count는 가장 작은 걸 선택해야 한다.
if diff_count == 1 and min_count >= target_compare_count and visited[index] == False:
next_word = word
min_count = target_compare_count
now = index # 방문 체크를 위한 index
begin = next_word
visited[now] = True
reps += 1
if begin == target: # next_word를 이용해 바꾼 현재 단어가 target과 같다면
break
elif all(visited): # 모든 단어들에 방문을 했는데 target과 같지 않다면
reps = 0
break
return reps신기하게도 모든 케이스에서 정답 처리를 받을 수 있었다.
뭔가 전혀 dfs 같지 않았고 그냥 구현 문제를 푸는 느낌이었다.
그래도 맞아서 기분이 좋았다.
다른 사람들의 풀이를 보니 뭔가 나의 풀이와 비슷한 면이 있어서 신기하기도 했다.
아래는 내가 생각한 깔끔한 코드이다.
from collections import deque
def get_adjacent(current, words):
for word in words:
if len(current) != len(word):
continue
count = 0
for c, w in zip(current, word):
if c != w:
count += 1
if count == 1:
yield word
def solution(begin, target, words):
dist = {begin: 0}
queue = deque([begin])
while queue:
current = queue.popleft()
for next_word in get_adjacent(current, words):
if next_word not in dist:
dist[next_word] = dist[current] + 1
queue.append(next_word)
return dist.get(target, 0)여기서 yield라는 예약어를 새로 배울 수 있었고 딕셔너리의 메소드인 get의 사용법에 대해 추가로 알 수 있었다.
yield는 return과 비슷하지만 return과는 달리 제네레이터라는 성격을 가지고 있다.
즉, 한 가지 값이 아닌 여러 가지 값을 yield에 저장하여 함수에서 반환시킬 수 있는 것이다.
심지어 제네레이터라는 특성상 필요로 할 때만 메모리가 차지돼기 때문에 효율도 좋다. (range로 숫자를 생성할 때와 같다.)
저렇게 get을 쓰면 나는 target이라는 key를 가지는 그리고 value는 0인 요소가 딕셔너리에 추가되는 줄 알았다.
하지만 그것이 아니라, get은 입력한 key가 "없다면" 뒤에 적어주는 default value를 적용해 새로운 요소를 만들어 주는 것이었다.
위의 코드처럼 get을 적어준다면(이미 target이라는 key가 딕셔너리에 존재하는 상황이라면) dict[target]과 같이 작동하게 된다.
즉, 그 값을 찾아준다.
dist[next_word] = dist[current] + 1이 아주 직관적이라고 생각해서 위의 코드가 마음에 들었다.
위의 get_adjacent도 마음에 들었다.
느낀점
배워도 다시 보면 새로운 느낌이 드는 게 개발 공부인 것 같다.
그래도 흥미를 느끼고 있다는 것에 행복하다.
이렇게 하나씩, 조금씩이라도 하다보면 성장한 모습을 발견할 수 있지 않을까 기대해본다.