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

출처 : 프로그래머스 코딩테스트 연습, https://programmers.co.kr/learn/courses/30/lessons/43163

코딩테스트 연습 - 단어 변환

 

이 문제는 오답인 풀이가 정답으로 통과되는 경우가 있다.

잘 체크해 볼 것.

 

 

BFS 풀이 : 틀림

 

def calcDistance(x, y):
    count = 0
    
    for i in range(len(x)):
        if x[i] != y[i]:
            count += 1
            
    return count

def solution(begin, target, words):
    #BFS
    
    visited = [False for _ in range(len(words))] #방문 체크 배열
    stack = [begin] #word를 넣는 stack
    stack_len = len(stack)
    count = 0 # count를 어떻게 셀까
    find = False
    
    while stack: #stack이 비었으면 return 0
        word = stack.pop()
        stack_len -= 1
        
        if word == target:
            count += 1
            find = True
            break
        
        for index in range(len(words)):
            if not visited[index]:
                if calcDistance(word, words[index]) == 1:
                    visited[index] = True
                    stack.append(words[index])
        
        if stack_len == 0:
            count += 1
            stack_len = len(stack)
                
    return count if find else 0

 

count를 체크하는 과정에서 queue의 방식을 전제로 두고 층수를 계산하도록 짰는데

막상 stack으로 작성해서 틀렸다.

 

BFS 풀이 : 정답

 

from collections import deque

def calcDistance(x, y):
    count = 0
    
    for i in range(len(x)):
        if x[i] != y[i]:
            count += 1
            
    return count

def solution(begin, target, words):
    #BFS
    
    visited = [False for _ in range(len(words))] #방문 체크 배열
    queue = deque([begin]) #word를 넣는 queue
    len_queue = len(queue)
    count = 0
    find = False
    
    while queue: #stack이 비었으면 return 0
        word = queue.popleft()
        len_queue -= 1

        if word == target:
            find = True
            break
        
        for index in range(len(words)):
            if not visited[index]:
                if calcDistance(word, words[index]) == 1:
                    visited[index] = True
                    queue.append(words[index])
        
        if len_queue == 0:
            count += 1
            len_queue = len(queue)
                
    return count if find else 0

 

일단 최소 몇 단계의 과정을 거쳐 라는 말이 나왔기 때문에 BFS로 접근하였다.

층수를 계산하는 부분에서 어려움을 겪어서 DFS로 풀어야하나 생각했는데 잘 고민했더니 BFS로도 풀 수 있더라.

---

 

시간 복잡도

 

-

 

알게 된 점

 

BFS에서 지나온 층을 어떻게 계산할까?

 

 

다음과 같은 트리를 BFS를 통해 계산한다고 하자.

지나온 층수를 계산하는 방법은 다음과 같다.

 

Pop Node	Queue	Count / Floor	Action
	[1]	1 / 0	Queue 길이 계산
1	[2, 3]	0 -> 2 / 1	Pop 1 Push 2, 3 Count -= 1 Count = 0 : (Floor += 1, Queue 길이 계산)
2	[3, 4, 5]	1 / 1	Pop 2 Push 4, 5 Count -= 1
3	[4, 5, 6, 7]	0 -> 4 / 2	Pop 3 Push 6, 7 Count -= 1 Count = 0 : (Floor += 1, Queue 길이 계산)
4	[5, 6, 7]	3 / 2	Pop 4 Count -= 1
5	[6, 7]	2 / 2	Pop 5 Count -= 1
6	[7]	1 / 2	Pop 6 Count -= 1
7	[]	0 / 3	Pop 7 Count -= 1 Count = 0 : (Floor += 1, Queue 길이 계산)

 

처음 시작 시에 Queue의 길이를 계산하고 Count라는 변수에 저장한다.

그 후 Pop 할 때 마다 Count라는 변수를 감소시킨다.

이러면 Count가 0이 될 때, 이전 층의 모든 노드를 검사하고 Queue에 다음 층의 모든 노드가 들어가있는 상태이기 때문에

다음 층의 노드 개수를 Count에 업데이트하여 층수를 정확히 계산할 수 있다.

 

고찰

 

모 기업 부트캠프 코딩테스트에서 그래프에서 비슷하게 층수를 계산해야하는 문제가 나왔었는데

그 때, 별 짓을 다하면서 시도하다가 구현을 못했던 기억이 난다.

 

Github

프로그래머스 - 단어 변환