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

문제링크

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

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

 

문제풀이

이 문제는 begin 이라는 문자열을 몇 번 변환해서 target 이라는 문자열로 만들 수 있는지 묻는 문제이다.

이 문제에 핵심 아이디어는 BFS 를 사용해서 푸는것이다.

먼저 words 문자열 안에 target 이라는 문자열이 존재하지 않으면 0 을 리턴하는 예외처리를 해준다.

그 다음, 처음 주어진 단어를 1번 변환해서 얻을 수 있는 단어들을 [word, 1] 형태의 리스트로 queue 에 집어넣는다. ( bfs 식 접근 ) 

그리고 리스트에 들어간 단어들은 방문처리를 해준다.

다음으로 단어를 2번 변환해서 얻을 수 있는 단어들은 현재 queue 에 들어있는 단어들을 토대로 알 수 있다.

이런식으로 변환을 k 번 할때, 변환된 단어중에서 target 과 같은 단어가 있으면, count 를 리턴해주면 된다.

 

visited 처리와 isOneCharDiff 함수만 잘 작성해주면 풀 수 있는 문제이다.

 

소스코드

from collections import deque;


def solution(begin, target, words):
    ans = 0;
    if (target not in words):
        return ans;
    
    #Make visited 
    visited = {};
    for w in words :
        visited[w] = 0;
    return BFS(begin, words, visited, target)

#SET
def isOneCharDiff(a,b):
    cnt = 0;
    for i in range(len(a)):
        if a[i] != b[i]:
            cnt += 1;
    if cnt == 1:
        return True;
    else:
        return False;
    
#BFS
def BFS(begin,words,visited,target):
    
    queue = deque();
    queue.append([begin, 0]);
    
    while(queue):
        [nowWord, cnt] = queue.popleft();
        
        # while 문 종료조건
        if (nowWord == target):
            return cnt;
        # 로직
        for w in words:
            if (visited[w] == 0 and isOneCharDiff(nowWord, w)):
                visited[w] = 1;
                queue.append([w, cnt + 1]);
    return 0;