[코테 연습] 단어 변환 Python

오늘도 뜬뜬 위젼은 뜬뜬 코테 연습을 한다네~

오늘은 오후 내내 인공지능 공부를 쫌 했더니 뿌듯한 하루다 ^>^!

 

https://weejw.tistory.com/377

[코테 연습] 네트워크 Python

 

저번에 dfs 실패했을 때, 다른 분 블로그에서 본 코드를 공부해서 참고해서 풀었다. 행운의 분~~!! 이 분덕분에 오늘 문제는 무려 30분도 안되서 코드가 작성이 되긴 했다! 

 

문제 설명

두 개의 단어 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 합니다.

---

첫 번째 시도 

minStep = 50

def dfs(currentWord, words, step, target):
    if currentWord != target:
        wordArr = copy.deepcopy(words)
        wordArr.remove(currentWord)
        step += 1
        for word in wordArr:
            if len(set(currentWord) - set(word)) == 1:

                dfs(word, wordArr, step, target)

    if currentWord == target:
        global minStep
        minStep = min(minStep, step)

def solution(begin, target, words):
    if target not in words:
        return 0

    for word in words:
        if len(set(begin) - set(word)) == 1:
            dfs(word, words, 1, target)

    return minStep

테스트 1 〉	통과 (0.04ms, 10.9MB)
테스트 2 〉	통과 (2.93ms, 10.8MB)
테스트 3 〉	실패 (1.58ms, 10.8MB)
테스트 4 〉	통과 (0.08ms, 10.7MB)
테스트 5 〉	통과 (0.04ms, 10.8MB)

음,, 그래 그래도!!!!! 으이 ! 4개나 통과하고! 

 

질문 게시판에서 나와 같은 상황이 발생하는 사람을 발견했다. 문제는 단어의 순서를 고려치 않은 코딩이였다. 그 분도 나랑 똑같이 set을 썼다 ㅋㅋㅋ 생각이 다 거기서 거기군,,

 

그럼 순서를 고려해서 단어를 비교해야 한다.  

 

그러면 인덱스를 넣어줘야하니까..

 

import copy

minStep = 50
def dfs(currentWord, words, step, target):
    if currentWord != target:
        wordArr = copy.deepcopy(words)
        wordArr.remove(currentWord)
        step += 1
        for word in wordArr:
            compareWord = zip(currentWord, word)

            cnt = 0
            for twoWord in compareWord:
                if twoWord[0] != twoWord[1]:
                    cnt += 1
            if cnt == 1:
                dfs(word, wordArr, step, target)

    if currentWord == target:
        global minStep
        minStep = min(minStep, step)


def solution(begin, target, words):
    if target not in words:
        return 0

    for word in words:
        compareWord = zip(begin, word)

        cnt = 0
        for twoWord in compareWord:
            if twoWord[0] != twoWord[1]:
                cnt += 1

        if cnt == 1:
            dfs(word, words, 1, target)

    return minStep

테스트 1 〉	통과 (0.06ms, 10.8MB)
테스트 2 〉	통과 (0.18ms, 10.8MB)
테스트 3 〉	통과 (0.58ms, 10.9MB)
테스트 4 〉	통과 (0.05ms, 10.8MB)
테스트 5 〉	통과 (0.05ms, 10.8MB)

네트워크를 거진 이틀 내내 풀어서 그런지 이건 30분만에 풀어서 기분 진짜 완전 좋고 막 파티해야하고 ㅠ

파티한다 오늘 광광운다 ㅠ 다른사람들이 보면 뭘 저거가지고 그러겠냐겠다..,, 수치사 꿱 그래도 지원이 잘했어요~

 

오늘밤 화려한 조명이 감싸는 파티 주인공 누구수깡!!!!!!