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

문제설명

단어 begin에서 단어 target으로 words 내에 있는 단어만을 이용해서 이동.

조건은 words단어 이동시 1글자만 달라야 한다.

중요한 조건으로 begin,target,words내 단어들의 글자수는 모두 동일하다.

접근

DFS로 접근해야하나 어떻게 해야 효율적으로 접근할 수 있을지 고민해보았다.

방법1 begin기준 a~z모두 고려

begin의 단어에서 한단어씩 a~z까지 바꿔가며 words내에 있으면 선택하는 방안.

단어의 길이는 최대 10이므로 (26*(words의 길이))^10이 된다. 시간초과나오기 딱 좋다. 어차피 words 단어 내에서 선택해야하는 것 아닌가? words단어에서 1글자 차이나는 것들을 선택하는 방법으로 가보자.

방법2 begin과 target간 다른 문자들만 고려

만약 begin이 hot, target이 him 이라면 왼쪽으로 부터 2,3번째 자리만 고려해주면 되는 것이 아닐까? 라는 생각을 했지만 빙 돌아가는 경우가 존재한다. 예를 들어 words에 hrt xrm xim him 이라한다면 값이 다른 경우도 고려해줘야하기 때문. 따라서 적절치 않다.

방법3 words기준 고려

words기준으로 탐색을 실시한다. 최소값을 구하는 것이므로 BFS로 접근했다.

한편, 일반적으로 BFS는 큐로 구현하나 문제가 있다

• deque를 구현하기엔 시간이 오래걸린다. 그렇다고 모듈을 사용하고 싶진 않다
• list으로 단순히 queue를 구현하기엔 pop(0)시 인덱스 정렬하는데 시간이 걸린다.
• 원형 큐를 구현하기엔 에러가 발생할 수 있다.(자료형 에러나지 않도록 다시 공부하자...)
• 위를 구현하고 방법의 수를 표현하기 위해 queue의 size만큼 pop한다면.? 나중에 해보자.

따라서 단순히 stack으로 pop하고 다음 stack에 전달해주는 방식으로 접근할 것이다.

구현

def FindCsdList(begin,words):
    csdList = []
    n = len(begin)
    for word in words:
        cnt = 0
        for i in range(n):
            if begin[i] != word[i]:
                cnt += 1
        if cnt == 1:
            csdList.append(word)
    return csdList

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

    words = set(words)

    repTime = len(words)-1
    flag = False

    csdList = FindCsdList(begin,words)

    curStack = []
    for csdBegin in csdList:
        if csdBegin == target:
            return 1
        curStack.append([csdBegin,words-{csdBegin}])

    for rep in range(repTime):
        nxtStack = []
        while curStack:
            csdBegin,remainWords = curStack.pop()
            csdList = FindCsdList(csdBegin,remainWords)
            for nxtBegin in csdList:
                if nxtBegin == target:
                    return rep+2
                nxtStack.append([nxtBegin,words-{nxtBegin}])
        curStack = nxtStack

    return 0

문제점

최단거리를 구하는 문제와 같다. 따라서 이미 방문한 단어이면 선택할 필요가 없다. 이전에 말한 것 처럼 최단거리여야 하므로 방문한 이후의 경로는 동일하므로 이전에 방문한 것이 최단거리이기 때문. u+v < x+u+v (u는 방문한 노드 v는 도착지점까지 노드길이 x는 돌아온 길이)

하지만 나는 또 그러지 못했다. 방문한 지점을 계속 저장하며 다녔다. words-{nxtBegin}으로 말이다. 이는 오버헤드가 매우 크므로 이러한 문제를 고려할 땐 중복 방문을 고려할 필요가 없는지 꼭! 생각해봐야할 것이다.