[프로그래머스] 단어 변환 ( DFS/깊이우선탐색/파이썬/Python)

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

 

 

 

 

문제 설명

두 개의 단어 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 cnt

 Python 전체 코드

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 사용법을 배웠다.

코드를 조금 깔끔하게 바꾸면 테스트 케이스에서 오류가 나는데 

방법은 똑같은데 어느 부분에서 틀린 건지 모르겠다.