[알고리즘] 프로그래머스 단어 변환

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

프로그래머스

프로그래머스 단어 변환 문제를 풀어보겠습니다.

 

풀이 방법

주어진 words를 단어로 변환해 target과 일치하는지 확인하는 과정으로 접근했습니다.

따라서 words 중 변환이 가능한 단어들로 그래프를 만들고 begin이 변환될 수 있는 모든 후보군을 찾아 최단거리를 찾았습니다.

결과값 중 가장 작은 값을 return 합니다.

 

최단거리를 찾기 위해 BFS를 적용했습니다.

인접리스트 형태로 그래프가 구현되어있기에

• \( O(V+E) where 3 \leq V, E\leq 50 \)

두 단어를 비교해 변환 가능한지 확인

• \(O(N) where 3 \leq N \leq 10 \)

접근 방식을 기반으로 충분히 풀이가 가능하다 판단됩니다.

코드

from collections import deque

graph = []


# 최단거리 반환 함수 -> BFS 활용
def find_route(start, target, lim):
    q = deque()
    q.append((start, 1))
    visited = [0] * lim
    while q:
        node, cost = q.popleft()
        if node == target:
            break
        visited[node] = 1
        for next in graph[node]:
            if visited[next] == 0:
                q.append((next, cost+1))
    return cost


# 두 str 비교 후 변환 가능한지 확인
def comp_str(a, b):
    n = len(a)
    count = 0
    for i in range(n):
        if a[i] == b[i]:
            count += 1
    if count == n-1:
        return True
    return False


def solution(begin, target, words):
    if target not in words:
        return 0

    global graph
    lim = len(words)
    # 그래프 찾기
    graph = [[] for _ in range(lim)]
    for i in range(lim):
        for j in range(i+1, lim):
            if comp_str(words[i], words[j]):
                graph[i].append(j)
                graph[j].append(i)
    cand = []
    target = words.index(target)
    # begin이 변환될 수 있는 모든 후보군 찾기
    for i in range(lim):
        if comp_str(begin, words[i]):
            cand.append(i)
    # 최소값 비교니 answer을 worst case에서 여유있는 55로 설정
    answer = 55
    # 각 후보 word에 대해 최단거리 구해서 global 최단거리 찾기
    for node in cand:
        route = find_route(node, target, lim)
        if route < answer:
            answer = route
    # 결과 리턴
    if answer != 55:
        return answer
    else:
        return 0