[프로그래머스 DFS/BFS]단어 변환 - Python3

문제

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 함수를 작성해주세요.

제한사항

• 각 단어는 알파벳 소문자로만 이루어져 있습니다.
• 각 단어의 길이는 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

 

 

알고리즘

def comparison(str1, str2):
    answer = 0
    for i in range(len(str1)):
        if str1[i] == str2[i]:
            answer += 1
    if answer == len(str1)-1:
        return True
    else:
        return False


def bfs_solution(begin, target, words):
    # target이 words안에 없다면 단어 변환을 할 수 없으므로 0을 리턴한다.
    if target not in words:
        return 0

    # 딕셔너리를 선언한다.
    # 이 딕셔너리의 key는 각 단계를 나타내는 정수이고, value는 그 단계에서 만들수 있는 모든 단어의 배열이다.
    graph = dict()
    graph[0] = [begin]

    # i는 graph의 key로 들어갈 값이다. 즉, 각 단계를 나타낸다. 그리고 temp배열을 만들어놓는다.
    for i in range(1, len(words)):
        print("i: ", i)
        temp = []

        # j라는 인덱스는 i-1번째 단계의 value, 즉 i-1번 변환해서 만들 수 있는 단어들의 배열을 순회한다.
        # 각 원소를 comp로 지정한다.
        for j in range(len(graph[i-1])):
            print("j:", j)
            comp = graph[i-1][j]

            # k라는 인덱스는 words배열의 다른 단어들을 순회한다.
            for k in range(len(words)):
                print("k: ", k)
                
                # words의 단어들을 순회하면서, comp와 comparison했을 때 True인 원소들을 temp에 append한다. 
                if comparison(comp, words[k]):
                    temp.append(words[k])
                    
        # temp 안에 target이 있다면, i를 리턴한다
        if target in temp:
            return i
    
        # 그렇지 않다면, graph의 key인 i에 value로써 temp를 지정한다. 
        graph[i] = temp

설명

이 문제를 풀기 위해서 BFS를 사용했다. 너비 우선 탐색을 하면서, 다음 단계에 만들 수 있는 단어들 중에 target이 있다면 그 순간 결과를 return하면 되기 때문이다. dfs처럼 그래프의 리프노드까지 갈 필요가 없다. 

내가 만들고자 한 데이터 형태는 다음과 같다. 

key (start 단어에서 단어를 변환한 횟수)	value (start단어에서 key만큼 단어를 변환할때 만들 수 있는 단어들의 배열)
0	[hit]	hit이라는 단어를 0번 변환하면 hit밖에 얻을 수 없다.
1	['hot']	hit을 1번 변환해서 얻을 수 있는 단어들의 배열이다
2	['dot', 'lot']	hit을 2번 변환해서 얻을 수 있는 단어들의 배열이다 또한, ['hot']을 1번 변환해서 얻을 수 있는 단어들의 배열이기도 하다.
3	['hot', 'dog', 'lot', 'hot', 'dot', 'log']	hit을 3번 변환해서 얻을 수 있는 단어들의 배열이다 또한, ['dot', 'lot']를 1번 변환해서 얻을 수 있는 단어들의 배열이기도 하다.
4	['dot', 'lot', 'dot', 'log', 'cog', 'hot', 'dot', 'log', 'dot', 'lot', 'hot', 'dog', 'lot', 'dog', 'lot', 'cog']	단어를 4번 변환했을 떄 cog라는 tarrget단어를 얻을 수 있다. 따라서, 4가 정답이다.

위처럼 만들기 위해, 3중 for문을 사용했다. 시간 복잡도가 걱정되지만, 달리 방법을 찾지 못했다. 그리고 입력 단어의 갯수도 50개 미만이라 괜찮을 거라 생각했다. 

1. 인덱스 i, j, k를 사용한다. i를 사용해서 각 단계에 해당하는 key를 생성해서 graph의 key로 지정하고, 
2. j를 사용해서 그 전 단계의 value를 불러온다
3. 그 불러온 전 단계 value의 원소들을 words와 비교해서, 그 다음 단계의 배열을 만들어서 graph[i]의 value로 지정한다.
4. 그리고, 새로 만들어진 배열에 target단어가 있다면 i를 리턴한다. 

결과

올바른 결과를 출력한다. 맨 밑줄에 출력된 4가 정답이다. 사진이 옆으로 길어서 좀 안보이는데, 위에 출력된 것들은 딕셔너리 형태의 graph이다. 자세히 보고싶으면 위에 표 참조하셈

 

후기 

이거 dfs로 푸는줄알고 몇시간을 삽질을 하다가 도저히 안될것같아서 bfs로 해봤는데, 갑자기 딕셔너리 생각이 나서 이렇게 풀었다. 으으 진짜 삽질을 너무해가지고 개짱났다. 근데 이렇게 푸니까 엄청 깔끔하게 잘 풀린거같은 느낌이다.

이건 dfs로 풀 필요가 없다. 왜냐면 정해진 데이터의 leaf노드까지 가면서 탐색할 필요가 전혀 없기 때문이다. 그냥 만들 수 있는 단어들을 전부다 만들어 보면서, 원하는 단어가 나오면 거기서 return하고 끝내면 된다. 근데 그런줄도 모르고 그냥 dfs하다가 고생했다.