프로그래머스 - 단어 변환(Level 3)/Wanna Be 컴잘알

문제 출처 : https://programmers.co.kr/learn/courses/30/lessons/43163?language=python3

프로그래머스

 

-문제-

 

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

1. 한 번에 한 개의 알파벳만 바꿀 수 있습니다. 2. words에 있는 단어로만 변환할 수 있습니다.

예를 들어 begin이 hit, target가 cog, words가 [hot,dot,dog,lot,log,cog]라면 hit -> hot -> dot -> dog -> cog와 같이 4단계를 거쳐 변환할 수 있습니다.

두 개의 단어 begin, target과 단어의 집합 words가 매개변수로 주어질 때, 최소 몇 단계의 과정을 거쳐 begin을 target으로 변환할 수 있는지 return 하도록 solution 함수를 작성해주세요.

제한사항

• 각 단어는 알파벳 소문자로만 이루어져 있습니다.
• 각 단어의 길이는 3 이상 10 이하이며 모든 단어의 길이는 같습니다.
• words에는 3개 이상 50개 이하의 단어가 있으며 중복되는 단어는 없습니다.
• begin과 target은 같지 않습니다.
• 변환할 수 없는 경우에는 0를 return 합니다.

입출력 예

begintargetwordsreturn

hit	cog	[hot, dot, dog, lot, log, cog]	4
hit	cog	[hot, dot, dog, lot, log]	0

입출력 예 설명

예제 #1
문제에 나온 예와 같습니다.

예제 #2
target인 cog는 words 안에 없기 때문에 변환할 수 없습니다.

 

-설명-

 

1. Python은 bfs로 c++은 dfs로 풀어봤는데, 주어지는 입력에 따라 어떤 알고리즘이 빠른지 다르겠지만 대체로 bfs가 빠르다고 생각하기 때문에 BFS기준으로 설명하겠습니다.

2. 알파벳 1개가 다를 경우 반환이 가능하므로 differCount라는 알파벳의 개수가 몇 개 다른지 반환해주는 함수를 하나 만들어줍니다. (실 구현에서는 불필요한 탐색을 막기 위해 2개 이상 다를경우는 break해서 더 탐색하지 않게함)

3. queue에 현재 begin 단어를 넣고  begin과 1개 언어가 다른 단어들을 찾아서 queue에 넣습니다. 단어의 개수를 쉽게 찾기 위해 한 뎁스에 있는 큐들은 다 처리해줍니다. -> loop = len(dq)   for k in range(loop)  //이 부분으로

4. 표로 진행되는 과정을 그려보면

변환개수	0(시작)	1	2	3	4
큐 상태	{hit}	{hot}	{dot,lot}	{dog,log}	{cog}

5. hit 에서 hot으로 이미 변환이 되었는데,  hot에서 hit으로 다시 변환되지않기위해 check 리스트로 방문체크를 해줍니다.

6. 타겟 word를 만나면 변환 개수를 반환시켜줍니다.

 

 

-코드-

 

Python

from collections import deque

def differCount(one, two):
    count = 0
    for i in range(0, len(one)):
        if one[i] != two[i]:
            count+=1
        if count >1:
            break
    
    return count

def bfs(begin,target, words):
    check = [False for i in range(len(words))]
    answer = 0
    sussessFlag= False
    dq = deque()
    dq.appendleft(begin)

    while len(dq) > 0:
        answer+=1
        loop = len(dq)
        for k in range(loop):
            curWord = dq.pop()

            for i,word in enumerate(words):
                if check[i]==False and differCount(curWord, word) ==1:
                    check[i] = True
                    dq.appendleft(word)
                    if word == target:
                        return answer

    return 0


def solution(begin, target, words):
    answer = bfs(begin, target, words)
    print(answer)
    return answer

C++

#include <iostream>
#include <string>
#include <vector>

using namespace std;

string cur;
bool check[51];
int minimum=2000000000;
string target_temp;
vector<string> words_temp;

void dfs(string cur, int cost){
    int cnt,which;
    if(cur == target_temp){
        if(minimum > cost){
            minimum = cost;
        }
        return ;
    }
    for(int i=0 ; i<words_temp.size(); i++){
        which=0;
        cnt=0;
        if(cur.length()==words_temp[i].size() && !check[i]){
            for(int k=0; k<cur.length();k++){
                if(cur[k]!=words_temp[i][k]){
                    cnt++;
                    which=k;
                }
            }
        }
        if(cnt==1){
            string temp = cur;
            temp[which] = words_temp[i][which];
            check[i] = true;
            dfs(temp,cost+1);
            check[i] = false;
        }
    }
}

int solution(string begin, string target, vector<string> words) {
    target_temp = target;
    words_temp = words;
    cur = begin;
    dfs(cur,0);
    if(minimum==2000000000)
        return 0;
    return minimum;
}