[Programmers_Python]단어 변환

문제

https://school.programmers.co.kr/learn/courses/30/lessons/43163

사용 알고리즘

BackTracking

BFS

 

풀이

고려사항

1. answer 변수 global 설정

2. 단어에서 한 부분만 다른지 확인

3. 지금 경로가 이미 최적 해를 넘었다면 이후 탐색은 필요 없음

4. target 도착 여부 확인

 

후기

1. 프로그래머스로 재귀나 백트래킹 등 함수를 만들어서 풀때 변수의 생명주기를 관리하는 것이 까다롭다.

백준의 경우 solution 함수가 따로 존재하지 않고 가장 밖에서 다른 함수를 호출하면 되기 때문에

가장 밖에 위치하고 있는 변수를 계속 함수에 매개변수로 들고 들어가지 않아도 관리 할 수 있지만,

함수에서 생긴 변수를 다른 함수에서 사용 할 때는 따로 관리해주어야 한다.

아래 코드에서는 answer 변수를 가장 밖으로 빼고 global로 관리하였다.

이렇게 하지 않고 solution에서 만든 후 backtracking 함수에서 global로 관리할 경우 

answer은 계속 solutiond의 1e9로 갱신되며 최소를 들고 있지 못하기 때문에 오류가 발생하기 때문이다.

2. 변수 생명주기만 관리한다면 이후 로직은 간단해진다.

두가지 방식이 있는데 우선 풀이했던 방식은 백트레킹 방식이고, 이후 다른 괜찮은 풀이는 BFS 방식이다.

3. 우선 백트레킹 방식의 경우 재귀적으로 모든 가능한 경로를 탐색한다.

현재 진행되고 있는 횟수와 answer(지금까지 탐색 중 최소 횟수)를 비교하여 가지치기를 진행하지만

그래프의 깊이가 깊거나 노드 수가 많을 경우 성능이 떨어질 수 있다.

4. 이에 반면 BFS 방식은 이미 방문한 곳은 최소의 횟수로 방문함을 고려해 더이상 가지 않기 때문에

시간측면에서 더 효율적이다.

 

 

코드

1. 백트레킹 방식 코드

answer = 1e9

def backtracking(cur, visited, temp_cnt, target, words):
    global answer
    
    if temp_cnt > answer:
        return
    
    if cur == target:
        answer = min(answer, temp_cnt)
        return answer
    
    for i in range(len(words)):
        if visited[i] == False:
            check = 0
            for j in range(len(cur)):
                if cur[j] != words[i][j]:
                    check += 1
            if check == 1:
                visited[i] = True
                backtracking(words[i], visited, temp_cnt + 1, target, words)
                visited[i] = False
    
    return answer

def solution(begin, target, words):
    global answer
    
    if target not in words:
        return 0
    
    visited = [False] * len(words)
    answer = backtracking(begin, visited, 0, target, words)
    
    return answer

 

2. BFS 방식 코드

from collections import deque

def bfs(begin, target, words):
    
    q = deque()
    q.append((begin, 0))
    
    visited = [False] * (len(words))
    
    while q:
        cur, cnt = q.popleft()
        
        if cur == target:
            return cnt

        for i in range(len(words)):
            check = 0
            if visited[i] == False:
                for j in range(len(cur)):
                    if cur[j] != words[i][j]:
                        check += 1
                if check == 1:
                    visited[i] = True
                    q.append((words[i], cnt + 1))
    return 0


def solution(begin, target, words):
    answer = 0
    if target not in words:
        answer = 0
    else:
        answer = bfs(begin, target, words)
    return answer

결과

백트레킹 방식 시간

BFS 방식 시간