[python] 프로그래머스 > DFS/BFS > 단어변환

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

 

- 입출력 예 설명

예제 #1
문제에 나온 예와 같습니다.

 

예제 #2
target인 cog는 words 안에 없기 때문에 변환할 수 없습니다.

 

<나의풀이 - 실패버전>

def solution(begin, target, words):
    answer = 0
    begin_list = list(begin) #['h','i','t']
    if target not in words:
        return 0
    else:
        for word in words:
            word_list = list(word) #['h','o','t']
            if word_list.count(begin_list[0]) + word_list.count(begin_list[1]) + word_list.count(begin_list[2]) == 2:
                answer += 1
                begin_list = list(word)
                words.remove(word)
        # print(words)
    return answer

<실패버전 해설>

words에서 begin의 값과 같은 문자가 2개 있는것을 어떻게 구분할까 하다가

begin의 str값을 list로 변환시키고, words에 있는 값을 하나하나 꺼내 str을 list로 바꾸어서 같은 문자가 2개 들어있다면 answer에 1을 더하고 해당 word값을 begin으로 초기화 시켜준 뒤에 해당 word값을 지워줬다.

 

<실패한 이유>

1. 위치에 상관없이 같은 문자가 2개만 있으면 바꿀 수 있는 줄 알았다. BUT 문자열의 위치와도 상관이 있었다.

2. for문을 words의 갯수만큼만 돌리고 끝내버리면 안됐다. pop을 사용해 문자열이 다른게 하나만 있을 경우 하나씩 꺼내서 다 꺼내졌을 때 까지 돌려야 했던 것이다.

 

 

<나의 풀이 - 성공버전 (다른 블로그 참조)>

global answer
def dfs(begin, target, words, visit):
    answer = 0
    stacks = [begin]
    while stacks:
        stack = stacks.pop()
        if stack == target:
            return answer
        
        for i in range(len(words)):
            if len([j for j in range(len(words[i])) if words[i][j] != stack[j]]) == 1:
                
                if visit[i] != 0:
                    continue
                visit[i] = 1
                stacks.append(words[i])
        answer += 1
    return answer

def solution(begin, target, words):
    if target not in words:
        return 0
    visit = [0 for i in words]
    answer = dfs(begin, target, words, visit)
    return answer​

 

<문제 해설>

1. 방문 여부를 words의 갯수만큼 0으로 초기화

2. words에 있는 한개 한개의 단어가 이전 비교값과 스펠링이 1개만 다르다면 방문여부를 true(1)로 변경하고 stacks에 추가한다.

3. for 문을 나오면 answer을 1개 추가한다.

4. stacks에서 pop으로 데이터를 꺼내 (pop으로 꺼낸게 또다시 기준값이 된다.) words에 있는 한개 한개의 단어와 비교하고 이미 방문값이 1이면 pass, 방문값이 0이면 1로 변경해준다.

5. target이 answers에 없다면 0을 return 해준다.

 

 

<다른사람의 풀이>

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)

 

from collections import defaultdict

def nextWord(cur, words):
    ret = []
    for word in words:
        cnt = 0
        for idx in range(len(word)):
            if word[idx] == cur[idx]:
                cnt += 1
        if cnt == len(cur)-1:
            ret.append(word)
    return ret

def bfs(begin, target, words):
    visited = defaultdict(lambda: False)
    queue = nextWord(begin, words)
    count = 0
    min = 1e9

    while(len(queue) > 0):
        size = len(queue)
        count += 1

        for _ in range(size):
            key = queue.pop(0)
            visited[key] = True
            if (key == target and count < min):
                min = count
            for candidate in nextWord(key, words):
                if (visited[candidate] == False):
                    queue.append(candidate)

    if min == 1e9:
        return 0
    else:
        return min

def solution(begin, target, words):
    answer = bfs(begin, target, words)
    return answer

 

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

 

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

    dfs(begin, target, 0, words)
    return answer

def change(fr, to):
    for i in range(len(fr)):
        if fr[:i]+fr[i+1:] == to[:i]+to[i+1:]:
            return True
    return False

def dfs(begin, target, d, words):
    global answer
    # print(begin)
    # print(words)
    if begin == target:
        # print(d)
        answer = d
        return
    else:
        if len(words) == 0:
            return 
        for w in range(len(words)):
            if change(begin, words[w]):
                word = words[:w]+words[w+1:]
                dfs(words[w], target, d+1, word)