DFS/BFS 완전정복기2 - 트리구조 탐색하는 방법

1. 문제

 

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 함수를 작성하세요

 

2. 제한사항

 

각 단어는 알파벳 소문자로만

 

각 단어의 길이는 3 이상 10 이하이며 모든 단어의 길이는 같다

 

words에 3개 이상 50개 이하의 단어가 있으며 중복되는 단어는 없다

 

begin과 target은 같지 않다

 

변환할 수 없는 경우에는 0을 return

 

3. 예시

 

 

4. 나의 풀이

 

이전에 배웠던 트리구조를 탐색하는 방식으로 deepcopy랑 deque를 이용해서 반복적으로 탐색하면 될 것같다

 

begin의 단어에서 오직 한글자만 바뀌어야 변환시킬 수 있으므로 words의 모든 단어와 begin을 비교 탐색해서 글자 하나만 다른지 검사를 해야할 것

 

해당되는 word는 여러개 있을 수 있어서 트리구조의 여러 경로로 변환 될것임

 

가장 먼저 target으로 나온 경우의 단계수를 return하면 될 것

 

def solution(begin, target, words):
    
    from copy import deepcopy
    from collections import deque
    
    if not(target in words):
        
        return 0
    
    else:

 

처음에 target이 words안에 없으면 절대로 변환이 불가능하므로 바로 0을 return함

 

다음 (현재단어, 탐색해야할 리스트, 단계수) 형식의 deque를 만들고 while 반복문으로 계속 돌리겠지

 

else:
    
    tf_list = deque([[begin, words, 0]])
    
    while 1:
        
        b,word_list,step = tf_list.popleft()

 

tf_list에서 하나씩 빼서 탐색을 시작

 

가장 먼저 변환이 가능한 단어는 오직 하나의 알파벳만 달라야하므로 현재 탐색할 word_list에서 알파벳이 하나만 다른 단어를 찾는다

 

for word in word_list:
    
    count = 0
    
    for x,y in zip(b,word):
        
        if x != y:
            
            count += 1
            
        if count >= 2:
            
            break

 

zip을 이용해서 b와 word를 동시에 순회하고 순회하면 단어를 구성하는 알파벳을 x,y로 가져오므로

 

x와 y가 다르면 count에 1을 더해준다

 

count가 2 이상이면 변환을 못하므로 더 검사하지말고 바로 break로 탈출함

 

    if count >= 2:


        break
    
if count == 1:
    
    if word == target:
        
        return step+1
    
    else:
    
        copy_word = deepcopy(word_list)

        copy_word.remove(word)

        tf_list.append([word,copy_word,step+1])

 

for문을 탈출해서 count가 1이면 word는 변환이 가능한 단어

 

만약 word가 target이면 현재 step에서 변환 한번한 단어가 word이므로 step+1을 바로 return함

 

target이 아니면 이제 word_list를 deepcopy하고 copy_word에서 word를 제거함

 

왜냐하면 word_list의 단어는 여전히 탐색해야할 단어가 남아있기 때문에 deepcopy하지 않고 제거하면 원본이 바뀌니까

 

아무튼 변환시킨 단어 word, 탐색해야할 단어 리스트 copy_word, 현재 스텝에서 1번 변환시켰으니 step+1을 tf_list에 넣어준다

 

def solution(begin, target, words):
    
    from copy import deepcopy
    from collections import deque
    
    
    if not(target in words):
        
        return 0
    
    else:
        
        tf_list = deque([[begin,words,0]])
        
        while 1:
            
            b,word_list,step = tf_list.popleft()
            
            for word in word_list:
                
                count = 0
                
                for x,y in zip(b,word):
                    
                    if x != y:
                        
                        count += 1
                    
                    if count >= 2:
                        break
                
                if count == 1:
                    
                    if word == target:
                    
                        return step+1
                    
                    else:
                    
                        copy_word = deepcopy(word_list)

                        copy_word.remove(word)

                        tf_list.append([word,copy_word,step+1])

 

5. 다른 풀이

 

좋아요를 많이 받은 풀이 몇가지 분석

 

def solution(begin, target, words):
    answer = 0
    
    Q = [begin]

    while True:
    
        temp_Q = []
        
        for word_1 in Q:
        
            if word_1 == target:
            
                 return answer
                    
            for i in range(len(words)-1, -1, -1):
            
                word_2 = words[i]
                
                if sum([x!=y for x, y in zip(word_1, word_2)]) == 1:
                
                    temp_Q.append(words.pop(i))

        if not temp_Q:
        
            return 0
            
        Q = temp_Q
        
        answer += 1

 

Q에 첫 단어 begin을 넣은 Q = [begin]

 

무한반복문 while True를 돌리고 temp_Q라는 빈 리스트 초기화

 

Q에서 단어 빼서 검사를 시작하는데 word_1이 target과 같으면 현재 answer = 0을 바로 return함

 

다음 if문이 통과안되면 for문을 도는데 range(len(words)-1,-1,-1)로 역순으로 순회를 하네 왜지?>

 

아무튼 words의 마지막부터 word_2라고 하는데 

 

이거 좀 지렸다 sum([x!=y for x,y in zip(word_1, word_2)])

 

for x,y in zip(b,word):
        
    if x != y:

        count += 1

    if count >= 2:

        break

 

내가 썼던 이걸 한줄로 바꿔버렸네

 

아무튼 두 단어 word_1과 word_2를 동시에 비교해서 알파벳 하나만 다르면 변환시킬 수 있다는 뜻이니까

 

words.pop(i)는 word_2를 의미하고 이걸 temp_Q에 넣어준다

 

Q를 모두 순회하고 나서 temp_Q가 없다면 target까지 변환시킬 수 있는 단어가 더 이상 없다는 뜻이므로 0을 return

 

temp_Q가 변환된 단어들의 모임이니까 이걸 Q로 바꾼다음에 answer가 변환된 step의 수니까 answer에 +1을 해주고

 

다시 temp_Q = []으로 초기화하고 Q에서 단어 하나씩 빼서 검사 반복

 

 for i in range(len(words)-1, -1, -1):
            
    word_2 = words[i]

    if sum([x!=y for x, y in zip(word_1, word_2)]) == 1:

        temp_Q.append(words.pop(i))

그리고 위에 보인것처럼 역순으로 순회하는 이유가 

 

만약 0부터 len(words)-1로 순회한다면.. 이게 마지막에 words.pop(i)에서 index가 꼬여

 

[0,1,2,3,4,5,6]에서 2를 제거하면 [0,1,3,4,5,6]으로 3번이 2번자리로 와버린단 말이지

 

그래서 3,4,5,6을 검사할때 3을 제거하고 싶은데 현재 i=3에서 words.pop(i)해버리면 4가 제거된다고

 

하지만 [0,1,2,3,4,5,6]에서 6번부터 시작하면 5번을 제거한다고 해도 [0,1,2,3,4,6]이고 

 

검사하지 않은 0,1,2,3,4는 index가 꼬이지 않아서 pop하는데 상관없다

 

 

6. 다른 풀이 2

 

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)

 

먼저 dist = {begin:0}이라는 사전을 초기화하고 queue = deque([begin])은 검사할 단어 초기화로 내가 쓴 tf_list와 비슷

 

queue가 존재할때까지 while반복문

 

현재 시작 단어가 current = queue.popleft()

 

그 다음 get_adjacent()함수를 봐야겠는데

 

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

 

words의 단어를 받아서 word라고 하고 current는 비교하고자하는 단어인데

 

길이가 다르면 스킵한다는데 길이가 다를리가 없는데 쟤는 지워도 되겠다

 

def get_adjacent(current, words):
    for word in words:
  

        count = 0
        for c, w in zip(current, word):
            if c != w:
                count += 1

        if count == 1:
            yield word

 

나랑 비슷하네? current랑 word 동시에 zip으로 비교해서 단어 수가 다를때마다 count에 1을 더해주고

 

for문 다 돈다음에 count가 1이면 yield word를 한다는데..

 

함수에 yield를 사용하면 제너레이터(generator)를 만든다고 함

 

그러니까 쉽게말하면 words의 단어 중에서 current와 알파벳이 하나만 다른 단어들이 (리스트는 아니지만 리스트처럼) 모여있다 이 말이야

 

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)

 

그래서 get_adjacent(current,words)를 통해서 words에서 current와 알파벳이 하나만 다른 단어들의 generator가 만들어져있고 

 

for문으로 generator 순회하면 하나씩 가져오잖어

 

next_word는 current와 알파벳이 하나만 다른 단어들이고

 

dist라는 사전에 next_word가 키로 존재하지 않으면

 

dist[next_word] = dist[current] + 1로 저장을 하는데

 

dist[current]는 current의 현재 스텝수이고 current가 한단계 변환되어 next_word로 되니까.. dist[next_word]는 next_word의 스텝수가 될거고

 

next_word도 그 뒤로 계속 변환시켜야할거잖아 queue에 넣어주고

 

queue가 없어서 while을 탈출하면 모든 경로를 검사했다는 의미가 될거고

 

dist.get(target,0)은 target이라는 key의 value를 가져오는거지.. value가 바로 target까지 변환시킬때 걸린 횟수일거고

 

target이 존재하지 않으면 변환시키지 못했다는 뜻이고 그런 경우는 0을 반환하게 될거고

 

 

7. 되돌아보기

 

앞에서 배운 deepcopy와 deque활용해서 트리구조 탐색 잘했다

 

다른 풀이 분석해보면 근본은 나랑 비슷해서리

 

sum([x!=y for x,y in zip(word_1, word_2)])

 

이런건 좀 지리긴하네 한줄로 처리해버리는

 

리스트 컴프리핸션이니까 속도도 더 빠를것 같은데

 

그리고 리스트를 pop으로 제거해야할때 인덱스 역순으로 제거하니까 인덱스가 안꼬인다는게

 

기억해놓으면 좋겠찌

 

사전의 get함수같은것도 기억해놓고 있으면 유용하겠지

 

yield라는 명령어? 기억해놓고있으면 유용할려나? 사실 굳이 yield를 써야했나 모르겠네 

 

8. 참고

 

https://dojang.io/mod/page/view.php?id=2412 

파이썬 코딩 도장: 40.1 제너레이터와 yield 알아보기