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

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

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

 

 

문제 설명

각 단어가 한 글자씩만 차이 나는 경우(ex. hot과 hit) 단어 변환이 가능합니다. 

단어들을 정점들로, 변환이 가능한 경우를 간선으로 표시해서 BFS를 이용해 문제를 해결했습니다. 

 

1. begin을 포함해서 그래프를 만들기 위해 words에 begin 단어를 삽입
2. 그래프를 표현하는 인접 리스트 초기화
3. 이때 두 단어가 정확히 "한 글자"만 차이 날 경우 인접한 걸로 간주
4. begin 단어 부터 BFS 수행
5. 이때 depth는 begin부터 현재 정점까지의 거리(변환 횟수)를 의미
6. BFS 중에 target에 도달하면 depth를 return

 

 

소스코드

from collections import deque

# word graph의 인접 리스트 초기화
def init_graph(graph, words):
    for i in range(len(words)):
        for j in range(len(words)):
            cnt = 0
            for k in range(len(words[i])):
                if words[i][k] != words[j][k]:  # 두 단어의 각 글자가 다를 경우
                    cnt += 1
                if cnt > 1: # 두 단어가 한 글자 이상 차이 나는 경우
                    break
            if cnt == 1:
                graph[i].append(j)


def bfs(start, target, words):
    graph = [[] for _ in range(len(words))]
    init_graph(graph, words)
    visited = [False] * len(words)
    depth = [0] * len(words)

    # BFS 시작
    queue = deque([start])
    visited[start] = True

    while queue:
        v = queue.popleft()
        for x in graph[v]:
            # 방문하지 않은 인접한 정점 방문
            if not visited[x]:
                queue.append(x)
                visited[x] = True
                # 현재 정점의 depth는 부모 정점의 depth + 1
                depth[x] = depth[v] + 1
                # target에 도달했을 경우
                if words[x] == target:
                    return depth[x]

    return 0   # target에 도달하지 못하는 경우


def solution(begin, target, words):
    answer = 0
    words.append(begin)
    # begin을 제일 뒤에 삽입 했으므로 begin의 인덱스는 words의 마지막 인덱스
    answer = bfs(len(words) - 1, target, words)
    return answer