프로그래머스 - 단어 변환(DFS/BFS)

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

 

# 풀이

- 단어와 단어 사이에 철자 차이를 계산해주는 함수(word_gap)를 정의한다.

- target이 words에 들어있지 않다면 0을 반환한다.

- 리스트(gaps)를 만들고 begin을 시작으로 단어 사이의 철자 차이가 1인 단어만 담고 꺼내가면서 계속 철자 차이가 1인 단어로

   begin을 바꿔가며 최종적으로 바뀐 begin이 target과 같으면 바꾼 횟수(result)를 출력한다.

def word_gap(w1, w2):
    gap = 0
    for i in range(len(w1)):
        if w1[i] != w2[i]:
            gap += 1
    return gap

def solution(begin, target, words):
    if target not in words:
        return 0
    
    gaps = [begin]
    result = -1
    while begin != target:
        begin = gaps.pop()
        for word in words:
            gap = word_gap(begin, word)
            if gap == 1:
                gaps.append(word)
        result += 1
    return result

 

# 고찰

- 시간 초과 판정을 받은 케이스가 있어 코드 수정이 필요하다.

- 아마 target으로 바꿀 수 없는 단어를 리스트(gaps)에서 꺼내게 되면 헛된 시간을 사용하기 때문인 것으로 판단된다.

- 도저히 개선 방안이 떠오르지 않아 인터넷 상 정답을 참고해서 내 코드를 수정해보았다.

 

# 수정된 풀이

- words에 인덱스로 접근해서 같은 단어로의 접근은 불가능하도록 해당 인덱스에 표시(True)를 해준다.

  -> DFS의 방문처리와 같은 원리

def word_gap(w1, w2):
    gap = 0
    for i in range(len(w1)):
        if w1[i] != w2[i]:
            gap += 1
    return gap

def solution(begin, target, words):
    if target not in words:
        return 0
    
    visit = [False] * len(words)
    gaps = [begin]
    result = -1
    while begin != target:
        begin = gaps.pop()
        for i in range(len(words)):
            gap = word_gap(begin, words[i])
            if gap == 1:
                if visit[i] == True:
                    continue
                visit[i] = True
                gaps.append(words[i])
        result += 1
    return result