[프로그래머스 코딩테스트 연습] BFS/DFS 3. 단어변환

BFS/DFS

3. 단어변환

 

---

문제 설명

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

테스트 케이스 

# test case 1
print(solution("hit", "cog",["hot", "dot", "dog", "lot", "log", "cog"] )) # 4

# test case 2
print(solution("hit", "cog", ["hot", "dot", "dog", "lot", "log"])) #0

---

솔루션 소스코드 

def solution(begin, target, words):
	if target not in words:
        return 0
        
    answer = 0
    stack = [begin]
    visited = [0] * len(words)
    
    while stack:
        cur = stack.pop()
        if cur == target:
            return answer
        
        for i in range(len(words)):
            diffCnt = 0
            for j in range(len(cur)):
                if cur[j] != words[i][j]:
                    diffCnt += 1

            if diffCnt == 1:
                if visited[i] == 0:
                    visited[i] = 1
                    stack.append(words[i])
                else:
                    continue
        answer += 1

    return answer

• 가장 먼저 target 단어가 words 리스트에 없으면 0 을 반환하도록 합니다.
• DFS에 사용할 스택을 선언하고, 시작 노드인 단어 begin을 저장해둡니다.
• 각 단어의 탐색 여부는 visited에서 관리해줍니다. 처음에는 모든 단어가 탐색되지 않은 상태이기 때문에 모두 0으로 세팅해줍니다.
• stack이 빌때까지, 즉 DFS에서 리프 노드에 도달하여 더 이상 탐색할 수 없을 때까지 탐색을 수행합니다.
• 루프 한번 돌 때 한번의 단어 변환이 발생하는 것이므로 while 루프의 끝에서 단어 변환 횟수를 나타내는 answer에 1을 더해줍니다. 
• while문 내부 
  • 스택 탑에서 현재 탐색 노드를 pop해서 cur에 저장합니다.
  • cur을 words에 있는 모든 단어와 비교를 합니다.
  • cur과 words[i] 단어의 각 알파벳을 비교하고 만약 cur[j]와 words[i][j]가 다르다면 diffCnt에 1을 더해줍니다.
  • diffCnt가 1인 word[i]만이 cur과 하나의 알파벳만 다른 단어이기 때문에 diff가 1인 단어만 방문합니다.
  • 만약 visited가 0이라면 아직 방문하지 않았으므로 1로 바꾸어 방문했음을 표시하고, 그 단어를 스택에 담아 다음 루프의 cur이 될 수 있도록 합니다. 
  • visited가 1이라면 이미 방문한 단어이므로 그냥 넘어가도록 합니다.
  • 만약 아직 방문하지 않았고, diffCnt가 1인 단어는 스택에 저장되어 다음 루프의 cur이 되고, 만약 없다면 다음 루프에서 스택은 빈 상태가 되므로 반복문이 종료됩니다. 
• 루프의 끝에서 탐색의 깊이를 나타내는 값이 answer가 반환되며 함수가 종료됩니다.