단어변환

it 취업을 위한 알고리즘 문제 풀이

문제

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

[

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

두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다. 1. 한 번에 한 개의 알파벳만 바꿀 수

programmers.co.kr

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

코드

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

from collections import deque, defaultdict

def isOneCharDiffer(str1, str2):
    charDifferCnt = 0
    for i in range(len(str1)):
        if str1[i] != str2[i]:
            charDifferCnt += 1
            if charDifferCnt >=2:
                return False
    else:
        if charDifferCnt == 1:
            return True     

def BFS(start, end, graph, checked):

    q = deque()

    q.append([start,0]) #[word,stage]

    while q:
        curWord, stage = q.popleft()

        if curWord == end:
            answer = stage
            return answer

        for nextWord in graph[curWord]: # 현재 단어와 연결된 단어 nextWord에 담기
            if not checked[nextWord]:
                checked[nextWord] = True
                q.append([nextWord,stage + 1])

def solution(begin, target, words):
    answer = 0

    if target not in words:
        answer = 0
        return answer
    else:
        if isOneCharDiffer(begin,target):
            answer = 1
            return answer

        # Graph 생성
        wordGraph = defaultdict(list)
        usedWord = defaultdict(bool)

        for word1 in words:
            if isOneCharDiffer(begin,word1):
                wordGraph[begin].append(word1)
                usedWord[begin] = False


            for word2 in words:
                if isOneCharDiffer(word1,word2):
                    wordGraph[word1].append(word2)
                    usedWord[word1] = False

        # BFS 탐색
        answer = BFS(begin,target,wordGraph,usedWord)

        return answer

문제해결방법

• isOneCharDiffer함수로 두 문자열을 매개변수로 전달하여 문자하나만 다른 경우를 찾는다.
  • 두 문자열의 0번 인덱스부터 비교하면서 다른 문자열이 발견되면 카운트 값을 하나 증가시킨다.
  • 카운트 값이 2가되면 문자열 비교 검사를 그만둔다.
  • 모든 문자열을 비교하고도 카운트 값이 1이면 두 문자열은 하나의 문자만 다른 문자열이다.
• 문자열을 비교해서 하나의 문자만 다른 문자열끼리 인접리스트 형태로 그래프를 생성한다.

• begin 단어부터 BFS탐색을 한다.