[Programmers] 단어 변환 (Python, BFS)

🌱 문제

프로그래머스

 

🌱 풀이

1. 해당 단어에서 바꿀 수 있는 단어 리스트 만들기 (그래프 만들기)

BFS 탐색을 할 것이기 때문에 현재 위치(현재 단어)에서 갈 수 있는(한글자 바꿀 수 있는) 위치를 담은 리스트(노드간 연결 정보를 담은 그래프)를 만들어야 합니다.

예를 들어, 단어 리스트가 hot, dot, dog, log, log, cog일 때, 그래프에는 아래와 같이 저장되어야 합니다. 

 

# 해당 단어에서 갈 수 있는 단어 정보 저장 (그래프 만들기)
for i in range(len(words)):
    word1 = words[i]
    for j in range(len(words) - i - 1):
        word2 = words[i + j + 1]
        if len([ch for idx, ch in enumerate(word2) if ch != word1[idx]]) == 1:
            graph[i].append(i + j + 1)
            graph[i + j + 1].append(i)

• 단어를 하나하나씩 비교해가면서 인덱스마다 비교했을 때 일치하지 않는 글자의 개수가 1개인 단어의 인덱스에 추가합니다. 무방향 그래프이므로 양쪽 모두 추가해줍니다.

 

2. 시작점 찾기

탐색을 시작할 시작점은 위에서 그래프를 만드는 방법과 동일합니다. begin으로 주어진 단어와 모든 단어를 비교하면서 begin과 한글자만 다른 단어의 인덱스를 start 리스트에 추가합니다.

for i in range(len(words)):
    word1 = words[i]

    if len([ch for idx, ch in enumerate(begin) if ch != word1[idx]]) == 1:
        start.append(i)

 

3. BFS 탐색하기

for s in start:
    answer.append(bfs(graph, s))

def bfs(graph, s):
    queue = deque()
    visited = [False for _ in range(len(words))]
    queue.append((s, 1))
    visited[s] = True

    while queue:
        v, step = queue.popleft()
        if words[v] == target:
            return step
        for i in graph[v]:
            if visited[i] == False:
                queue.append((i, step + 1))
                visited[i] = True

• start에 저장해놓은 단어의 인덱스들을 하나씩 돌면서 BFS 탐색을 합니다.
• BFS 탐색을 할 때에 queue에 글자가 바뀐 횟수를 함께 넘겨줍니다.
• queue에서 꺼낸 단어가 target과 같다면 현재까지 글자를 바꾼 횟수(step)을 리턴합니다.

 

🌱 정답

# !/usr/bin/env python
# -*- coding: utf-8 -*-
# programmers 단어 변환

from collections import deque

def solution(begin, target, words):
    answer = []

    graph = [[] for _ in range(len(words))]
    start = []

    if target not in words:
        return 0

    def bfs(graph, s):
        queue = deque()
        nonlocal words
        visited = [False for _ in range(len(words))]
        queue.append((s, 1))
        visited[s] = True

        while queue:
            v, step = queue.popleft()
            if words[v] == target:
                return step
            for i in graph[v]:
                if visited[i] == False:
                    queue.append((i, step + 1))
                    visited[i] = True

    # 해당 단어에서 갈 수 있는 단어 정보 저장 (그래프 만들기)
    for i in range(len(words)):
        word1 = words[i]
        for j in range(len(words) - i - 1):
            word2 = words[i + j + 1]
            if len([ch for idx, ch in enumerate(word2) if ch != word1[idx]]) == 1:
                graph[i].append(i + j + 1)
                graph[i + j + 1].append(i)

        if len([ch for idx, ch in enumerate(begin) if ch != word1[idx]]) == 1:
            start.append(i)

    for s in start:
        answer.append(bfs(graph, s))

    if min(answer) == None:
        return 0
    return min(answer)