[프로그래머스] 단어변환 - BFS, DFS 별 풀이

문제 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/43163

프로그래머스

 

 

조건을 만족하는 케이스를 기준으로 탐색을 해가며 최소로 만족하는 step 을 되는 문제이다.

최단거리랑 같은 개념으로 주로 BFS 를 사용한다면, 최소 step 에 return 을 하면 되기 때문에 BFS 방식을 추천한다.

아래 풀이 코드에선 BFS, DFS 두가지 방식으로 풀이를 했다.

 

def check(a, b):
    max_diff = 1
    for i in range(len(a)):
        if a[i] != b[i]:
            max_diff -= 1
            
        if max_diff < 0 :
            return False
        
    return True
    


def dfs(cur, tar, words, step):
    min_step = 99999
    # print(cur, tar, words)
    
    if cur == tar:
        print(step)
        return step
    if len(words) == 0:
        return 99999
    for i in range(len(words)): 
        if check(cur,words[i]):
            min_step = min(min_step,dfs(words[i], tar, words[i+1 : ] + words[:i], step+1))
            # dfs(words[i], tar, words[i+1 : ] + words[:i], step+1)
            
    return min_step
            

def bfs(begin, target, words):
    from collections import deque
    step = 0
    q = deque([(begin, step)])
    
    visited = {}
    while q:
        cur, step = q.popleft()
        
        if cur == target:
            return step
        else:
            for i in words:
                if check(cur,i) and visited.get(i) is None:
                    visited[i] = 1
                    q.append((i, step+1))
        print(step)
        step +=1
        
    return 0
    
                       
    
def solution(begin, target, words):
    
    # answer = dfs(begin, target, words, 0)
    # if answer == 99999: 
    #     return 0
    answer = bfs(begin, target, words)
    return answer