[프로그래머스] 단어 변환
문제 설명
두 개의 단어 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 함수를 작성해주세요.
입출력 예
| begin | target | words | return |
| "hit" | "cog" | ["hot", "dot", "dog", "lot", "log", "cog"] | 4 |
| "hit" | "cog" | ["hot", "dot", "dog", "lot", "log"] | 0 |
문제 풀이
DFS 깊이 우선 탐색
저는 DFS 깊이 우선 탐색을 사용하여 풀었습니다.
우선 루트를 begin으로 가지고 현재 노드에서 한 문자만 다른 단어를 자식 노드로 가지는 그래프를 만들어 줍니다.
그리고 그 그래프를 깊이 우선 탐색하면서 타깃 단어를 찾는 방법을 사용했습니다.
그래프 생성하기
begin에서 target으로 변환하는 과정 중 가장 짧은 경우를 찾아야 하므로
그래프를 생성하기 전 begin 노드를 맨 앞에 추가해 주었습니다.
그리고 현재 단어와 한 문자만 다른 단어들을 자식 노드로 가지는 그래프 graph를 생성합니다.
자식 노드들은 리스트로 한 번에 저장합니다(similar_node)
for문으로 words의 단어를 차례대로 확인합니다.
Counter 함수를 사용하여 현재 단어와 확인할 단어의 각 문자와 개수 센 다음(cnt1, cnt2)
어떤 문자가 몇 개가 다른지 비교하고(cnt1-cnt2),
그 요소들을 가진 리스트를 만듭니다. diff
이 리스트의 길이가 1이라면 두 단어가 한 문자만 다르다는 의미므로 similar_node에 추가합니다
만약 이 자식 노드 리스트에서 타깃 단어가 있을 경우 그 단어를 가장 먼저 방문하는 것이 가장 짧은 변환 과정이 되므로 리스트의 맨 앞으로 보내줍니다. dfs 사용할 것이기 때문에 스택에서는 먼저 들어가야 먼저 탐색될 수 있습니다.
Main 함수
def solution(begin, target, words):
# begin을 시작노드로 만들기 위해 words 리스트 맨 앞에 추가
words.insert(0,begin)
graph={}
#그래프 생성
for i in range(len(words)):
similar_node = []
#자식 노드 리스트 생성: 단어가 현재 문자와 한 문자만 다른 경우 자식 노드 리스트에 추가
for j in range(len(words)):
cnt1 = Counter(words[i])
cnt2 = Counter(words[j])
diff= list((cnt1-cnt2).elements())
if len(diff)==1:
similar_node.append(words[j])
#만약 타겟이 비슷한 단어 리스트에 있다면 가장 먼저 탐색할 수 있도록 리스트의 맨 앞 요소로 이동
if target in similar_node:
similar_node.remove(target)
similar_node.insert(0,target)
graph[words[i]] = similar_node
answer = dfs(graph,begin,target)
깊이 우선 탐색 하기
평범한 dfs 코드에서 다른 것은 스택에 다음 방문할 노드 삽입할 때인데
위에서 그래프를 생성할 때 타깃이 될 수 있는 노드는 리스트의 맨 앞에 넣어두었으므로
리스트의 맨 뒤부터 확인하여 아직 방문을 안 한 즉, visited리스트에 해당 단어가 포함되어 있지 않다면 추가해줍니다.
반복하여 탐색하고 현재 단어가 target과 같거나 스택이 비어있다면 탐색을 멈춥니다
만약 visited 리스트에 타깃이 없다면 0을 반환하고
있다면 현재까지 방문한 단어들에서 -1( begin 탐색할 때도 +1 해주었기 때문에) 해주고 반환합니다.
DFS 함수
def dfs (graph,root,target):
visited = []
stack =[root]
cnt = 0
while stack:
now = stack.pop()
cnt+=1
if now not in visited:
visited.append(now)
for i in range(len(graph[now])-1 ,-1,-1):
node = graph[now][i]
if node not in visited:
stack.append(node)
if now == target :
break
if target not in visited:
cnt = 0
else :
cnt = len(visited) -1
return cntPython 전체 코드
from collections import deque,Counter
def solution(begin, target, words):
words.insert(0,begin)
graph={}
for i in range(len(words)):
similar_node = []
for j in range(len(words)):
cnt1 = Counter(words[i])
cnt2 = Counter(words[j])
diff= list((cnt1-cnt2).elements())
if len(diff)==1:
similar_node.append(words[j])
if target in similar_node:
similar_node.remove(target)
similar_node.insert(0,target)
graph[words[i]] = similar_node
answer = dfs(graph,begin,target)
return answer
def dfs (graph,root,target):
visited = []
cnt = 0
stack =[root]
while stack:
now = stack.pop()
if now not in visited:
visited.append(now)
for i in range(len(graph[now])-1 ,-1,-1):
node = graph[now][i]
if node not in visited:
stack.append(node)
if now == target :
break
cnt+=1
if target not in visited:
cnt = 0
else :
cnt = len(visited) -1
return cnt
<새로 배운 것 >
처음에 그래프를 생성할 때 자식 노드를 연결할 때 set을 사용하여 문자열 비교를 했는데
이 경우는 문자가 여러 개 있는 경우 셀 수가 없음
예) aple과 appple는 apple과 차이가 없음 set이 중복을 삭제하기 때문
Counter 사용법을 배웠다.
코드를 조금 깔끔하게 바꾸면 테스트 케이스에서 오류가 나는데
방법은 똑같은데 어느 부분에서 틀린 건지 모르겠다.
