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

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

프로그래머스

 

문제 요약

2개의 단어 begin, target과 단어 집합 words가 주어진다.

한 번에 한 개의 알파벳만 바꿀 수 있고, words에 있는 단어로만 변환 가능하다.

 

'최소' 몇 단계의 과정을 거쳐서 begin을 target으로 바꿀 수 있는지,

최소 변환 횟수를 출력하기

 

변환할 수 없는 경우에는 0 반환

 

 

코드 설명

 

「1」

우선, bfs 활용한 풀이법이다.

 

def solution(begin, target, words):
    
    # target이 words 안에 없는 경우
    if target not in words:
        return 0
    
    return bfs(begin, target, words)

 

solution 함수에서

우선 words에 target이 있는지 확인하여 없는 경우는 변환이 불가능한 경우로 0 처리를 해준다.

 

변환이 가능한 경우에 대해서 bfs로 최소 변환 횟수를 구한다.

 

from collections import deque
def bfs(begin, target, words):
    q = deque()
    q.append([begin, 0])  # 시작 단어와 단계 0으로 초기화
    
    while q:
        now, step = q.popleft()
        
        if now == target:
            return step
        
        # 단어 집합을 전부 확인하면서
        for word in words:
            count = 0
        
            # 현재 단어의 알파벳들과 단어 집합의 한 단어 알파벳들을 비교
            for i in range(len(now)):
                if now[i] != word[i]:
                    count += 1
                    
            # 알파벳 하나만 다른 경우에 q에 삽입
            if count == 1:
                q.append([word, step + 1])   # 하나의 now에 대해 여러 개의 word가 큐에 삽입될 수 있다.

 

collections 라이브러리에서 deque 함수를 불러와서, 큐 자료구조를 활용해 bfs를 구현한다.

 

큐 역할을 할 변수를 선언하고, deque 함수를 불러와서 큐를 생성한다.

초기 단어인 begin과 변환 단계를 나타내는 0을 리스트 형태로 큐에 넣어준다.

 

큐가 빌 때 동안, 큐의 앞에서 원소를 꺼내서

목표 단어에 도달했는지 확인하고, 도달했다면 단계 step을 반환한다.

 

 

목표 단어에 도달하지 못한 경우에는,

단어 집합을 순회하면서

큐에서 빼낸 단어의 각 알파벳과 순회하고 있는 단어의 각 알파벳을 비교하는 과정을 거친다.

 

다른 경우에 count 변수를 +1 해주는데

만약 count 변수가 1인 경우라면, 단어 now에서 알파벳 하나만 변환해 만들 수 있는 단어이므로

큐에 해당 단어와 step을 1 늘려서 넣어준다.

 

 

「2」

dfs를 활용한 풀이법이다.

 

dfs는 크게

① 스택 자료구조를 활용한 구현

② 재귀 함수를 통한 구현

으로 나뉘는데,

 

①의 구현에서 스택은

    º 단순히 리스트로 구현

    º collections 라이브러리리의 deque로 구현

두 가지 방식으로 구현할 수 있다.

 

성능 면에서 리스트보다는 deque를 활용한 풀이가 좋다!

 

 

.

.

.

 

 

① 스택 자료구조를 활용한 구현

def solution(begin, target, words):
    answer = 0
    
    if target not in words:
        return 0
    
    visited = [0 for i in words]
    
    answer = dfs(begin, target, words, visited)
    
    return answer

 

우선 동일하게 target 단어가 words에 포함되어 있는지 확인한다.

 

포함되어 있다면, dfs를 돌려준다.

방문 여부를 확인하는 visited 변수를 사용하는 이유는

변환 횟수의 최소값을 구하라고 하였기 때문에, 이미 방문한(변환 시에 거쳐간) 단어는 방문하지 않기 위해서이다!

 

def dfs(begin, target, words, visited):
    count = 0
    stacks = [begin]
    
    while stacks:
        now = stacks.pop()
        
        if now == target:
            return count
        
        for w in range(0, len(words)):
            # 한 개의 알파벳만 다른 경우
            if len([i for i in range(0, len(words[w])) if words[w][i] != now[i]]) == 1 and visited[w] == 0:
                    
                # 방문하지 않은 단어이면 방문 처리하고 stacks에 추가
                visited[w] = 1
                stacks.append(words[w])
                
        count += 1
    
    return count

 

스택에 최초 단어를 넣어주고, 스택이 빌 때까지 반복을 해준다.

스택에서 최상단 원소를 꺼낸다.

 

최상단 원소가 목표 단어이면 변환 횟수인 count를 반환한다.

목표 단어가 아니라면, 단어 집합을 순회하면서 각 단어에 대해 일치하는 알파벳 개수를 확인한다.

 

[i for i in range(0, len(words[w])) if words[w][i] != now[i]]

 

위 구문의 의미는

각 단어의 길이만큼 순회하면서, 각 위치의 알파벳이 일치하지 않는 경우에 리스트에 i 값을 원소로 넣는다.

이렇게 채워진 리스트의 길이, 즉 len() 값이 1이라면 두 단어 사이에 하나의 알파벳만 다른 경우이기 때문에 문제의 조건과 맞는다.

그리고 '최소' 조건 만족을 위해 방문 여부도 체크를 해준다.

 

두 조건이 모두 만족된 경우에

해당 단어를 방문 처리 해주고, 스택에 넣어준다.

 

한 깊이가 탐색이 끝나면 count를 +1 해준다.

스택이 빌 때까지 반복하는데, 그 과정에서 목표 단어를 만나면 count 값, 즉 변환 횟수를 반환하고 종료된다.

 

 

아래 코드는 동일한 코드이지만, deque를 활용해 성능을 개선한 코드이다!

from collections import deque
def dfs(begin, target, words, visited):
    count = 0
    q = deque([begin])
    
    while q:
        now = q.pop()
        
        if now == target:
            return count
        
        for w in range(0, len(words)):
            # 한 개의 알파벳만 다른 경우
            if len([i for i in range(0, len(words[w])) if words[w][i] != now[i]]) == 1 and visited[w] == 0:
                    
                # 방문하지 않은 단어이면 방문 처리하고 stacks에 추가
                visited[w] = 1
                q.append(words[w])
                
        count += 1
    
    return count

 

 

② 재귀 함수를 통한 구현

def solution(begin, target, words):
    visited = [0 for i in words]
    # visited = [0] * len(words)
    
    result = dfs(begin, target, words, visited, 0)
    
    # 변환 경로가 없다면, 무한대 대신 0 반환
    return result if result != float('inf') else 0

 

target이 words 리스트에 없어서 불가능한 경우이든,

변환 과정에서 불가해서 변환이 불가능한 경우든,

두 경우 모두 result가 float('inf')이기 때문에, result 값에 조건을 걸어서 처리해 줄 수도 있다!

 

 words 리스트의 길이만큼의 0을 갖는 방문 여부 처리 변수의 선언은 두 가지로 표현 가능하다.

 

def dfs(current, target, words, visited, depth):
    if current == target:
        return depth
    
    min_count = float('inf')   # 양의 무한대 값 : 최솟값 구할 때 초기값으로 자주 사용된다!
    
    # 가능한 단어를 탐색
    for i in range(len(words)):
        if sum([1 for j in range(len(current)) if current[j] != words[i][j]]) == 1 and visited[i] == 0:
            visited[i] = 1
            count = dfs(words[i], target, words, visited, depth + 1)
            min_count = min(min_count, count)
            visited[i] = 0  # 백트래킹
    
    return min_count

 

현재 노드가 목표 단어이면, 깊이 반환하고 종료

 

아니라면,

단어 집합을 순회하면서 알파벳이 하나만 일치하고, 방문하지 않은 단어인 경우에만

dfs를 재귀적으로 사용한다.

백트래킹을 사용해 가능한 모든 변환 과정을 확인하면서, 변환 횟수가 최소가 되는 경우를 찾아야 최적의 해답을 구할 수 있다.

 

 

배운 점

- 꼭 그래프 형식으로 데이터가 주어지지 않아도, dfs/bfs 알고리즘을 사용할 수 있다

- 최단 경로를 구하는 문제에서는, 모든 경로를 확인하고 최소값을 구해야하기 때문에 백트래킹이 불가피하다! (백준 1987. 알파벳 문제 참고)

 

 

참고 자료

- https://data-marketing-bk.tistory.com/entry/DFS-%EC%99%84%EB%B2%BD-%EA%B5%AC%ED%98%84%ED%95%98%EA%B8%B0-%ED%8C%8C%EC%9D%B4%EC%8D%AC

- https://jie0025.tistory.com/486

- https://khann.tistory.com/79

프로그래머스 단어 변환 풀이 (파이썬)