[프로그래머스 43163 파이썬] 단어 변환 (level 3, BFS/DFS)

알고리즘 유형 : BFS/DFS
풀이 참고 없이 스스로 풀었나요? : O

https://school.programmers.co.kr/learn/courses/30/lessons/43163?language=python3

소스 코드(파이썬)

from collections import deque

def solution(begin, target, words):
    answer = 0
    # begin에서 변환될 수 있는 단어도 파악해야하므로 추가
    words.append(begin)
    graph = [[] for _ in range(len(words))]
    visited = [0]*len(words)
    
    # 각 단어에 대해, 그 단어와 words의 다른 모든 단어들과
    # 비교하여 변환가능한 단어를 연결 그래프로 나타내기
    for i in range(len(words)):
        word = words[i] # 기준 단어
        for j in range(len(words)):
            compared = words[j] # 비교할 단어
            cnt = 0
            for c_idx in range(len(word)):
                if word[c_idx] != compared[c_idx]:
                    cnt += 1
            if cnt == 1: # 한 글자만 다르면 변환 가능이므로 간선 정보 추가
                graph[i].append(j)
    
    q = deque([len(words)-1])
    visited[len(words)-1] = 1 # 출발 노드 재방문 방지를 위해 1 저장
    
    while q:
        word_num = q.popleft()
        
        if words[word_num] == target:
            # 출발 노드 visited가 1이었으므로, 1을 빼준 값이 답임
            answer = visited[word_num] - 1
            break
        
        for adj_word_num in graph[word_num]:
            if visited[adj_word_num] == 0:
                visited[adj_word_num] = visited[word_num] + 1
                q.append(adj_word_num)
    
    return answer

풀이 요약

1. 인접 노드를 어떻게 정의할건지가 핵심인 그래프 탐색 문제이다.

   문제에서 주어졌듯이 인접 노드의 성립 조건은, 단 하나의 글자만이 다른 언어여야 된다는 점이다.

   따라서, 모든 글자를 순회하면서, 각 글자와 words의 모든 글자 사이의 인접 노드 성립 조건을 검사하고, 성립하면 간선 정보를 연결 그래프 2차원 리스트에 추가해준다.

   최대 50개의 글자를 돌면서, 각 글자에 대해 words의 50개의 모든 글자와 인접 노드 성립을 검사하는데 글자의 최대 길이가 10이므로, 기껏해야 시간복잡도는 505010이다.

2. 그래프를 구성하고나면 BFS를 돌리면 된다.

   단, visited로 변환 횟수를 기록해나가야한다. 인접 노드로 나아갈 때, 원래의 visited 값에 1을 더한 값을 인접 노드의 visited로 삼는다.

   이 때, 인접 노드로 삼을 때 조건 중 하나는 visited가 0인 것. 즉 방문하지 않은 노드여야한다.

   그런데 출발 노드의 visited가 0이면, 나중에 재방문하게 되버리기에 출발 노드의 visited를 1로 설정 후, 나중에 BFS가 target에 도착할 때, 그 때의 visited 값에 1을 뺀 값을 저장해주면 된다.

배운 점, 어려웠던 점

• 인접 노드를 정의하는 아이디어를 떠올리는 과정에서 시간 복잡도를 잘못 생각해서 조금 애먹었다..