프로그래머스 (Lv3) - 단어 변환

링크 : 단어 변환

 

문제 해석

begin은 처음 시작하는 단어

target은 변환할 단어

words는 begin에서 바꿀 수 있는 알파벳들이 모인 단어의 리스트

 

처음에는 words에 있는 단어들의 알파벳들이 서로 연관이 있으면 연결해서 graph로 만들고 bfs로 접근 하려고 했었음

상상했던 그림

이렇게 구현해본 결과 test 케이스에서는 o라는 알파벳이 모든 단어랑 연결이 되고 알파벳을 딱 하나만 변화하는 단어를 찾는 방법을 또 고민해야 했었다. (중간에 방향을 틀게 된 계기)

 

최종적으로 begin에서 하나의 알파벳만 변경되는 단어를 찾고 해당 단어에 target이 있으면 탈출하는 코드를 만들게 됨.

def solution(begin, target, words):
    answer = 0
    # begin을 변경하기 전에 중복되는 단어로 선택하지 않기 위함
    pre = '' 
	
    # target이 words에 없으면 바로 0을 반환하도록
    if target not in words:
        return 0
    
    else:
        while True:
            list_ = [] ## 알파벳 하나만 바뀐 단어들을 넣어주기 위함
            for word in words:
                cnt = 0 # begin이랑 몇개의 알파벳이 중복되는지 알기 위함
                for a,b in zip(begin,word): # a == begin , b == word
                    if a == b:
                        cnt += 1
        		## 중복되는 단어가 하나 차이 나고, 이전 단어와 다르면 리스트에 추가
                if (cnt == len(word)-1) and (word != pre):
                    list_.append(word)
    		
            ## 위에서 단 하나만 차이나는 단어 중 target값이 있으면
            ## while 문 탈출
            if target in list_:
                answer += 1
                break
            ## 그렇지 않으면 pre는 이전 단어(begin)로 설정하고
            ## begin은 list_중 하나로 설정
            else:
                answer += 1
                pre = begin
                begin = list_[0]
    
        return answer

 

해당 문제는 프로그래머스 고득점 kit에서 BFS/DFS 카테고리로 나뉘어져 있었음

DFS, BFS로 안풀어서 뭔가 찝찝했음

 

그리고, 다른 사람의 풀이를 보니 굇수들이 너무 많음.. ㅠㅠ

열심히 코드 보고 배워야겠다 !!