프로그래머스 문제 - 단어 변환

프로그래머스 단어 변환 문제 풀이를 진행하였습니다.

문제 해석

문제를 읽으면 아래와 같은 해석이 가능합니다.

두 개의 단어 begin, target과 단어의 집합 words가 주어집니다.
다음의 규칙을 따라야 합니다.

규칙을 지키면서 begin의 단어를 target으로 변환시키는데 최소 몇 단계가 필요한지 출력해야 합니다.

문제 풀이

단어의 갯수와 길이가 길지 않으니 하나씩 찾아도 충분히 가능할 것이기 때문에 queue를 이용해보겠습니다.

일단 단어들을 queue에 전부 넣어줍니다. 단어의 길이는 전부 같으니 단어의 길이를 미리 변수에 저장해두었습니다.

queue<string> q;
for(string s : words)
{
    q.push(s);
}
wordSize = begin.size();

이후 DFS를 사용하여 현재 단어를 queue에 담긴 모든 단어들과 비교하여 한 가지만 다른 단어들을 찾아 진행해주었습니다.
만약 일치하는 단어가 없을 경우에는 무시하고 넘어가게 됩니다.

if(cur.compare(target) == 0)
{
    if(changeCount > cnt || changeCount == 0)
    {
        changeCount = cnt;
    }
    return;
}
int size = words.size();
for(int i = 0; i < size; i++)
{
	//현재 체크할 단어를 뽑아줌
    string checkWord = words.front();
    words.pop();
    int difCount = 0;
    //앞에서부터 한 단어씩 비교해줌
    for(int j = 0; j < wordSize; j++)
    {
        if(cur[j] != checkWord[j])
        {
            difCount++;
        }
    }
    //만약 한개의 단어만 다르다면 단어를 들고 함수 실행
    if(difCount == 1)
    {
        solve(checkWord, target, words, cnt+1);
    }
    //다음 단어들을 위해 빼두었던 단어를 다시 넣어줌
    words.push(checkWord);
    difCount = 0;
}

전체 코드

이번 문제는 DFS를 사용하여 문제를 해결할 수 있었습니다.

#include <bits/stdc++.h>
#include <string>
#include <vector>

using namespace std;

int changeCount = 0;
int wordSize = 0;

void solve(string cur, string target, queue<string> words, int cnt)
{
    if(cur.compare(target) == 0)
    {
        if(changeCount > cnt || changeCount == 0)
        {
            changeCount = cnt;
        }
        return;
    }
    int size = words.size();
    for(int i = 0; i < size; i++)
    {
        //현재 체크할 단어를 뽑아줌
        string checkWord = words.front();
        words.pop();
        int difCount = 0;
        //앞에서부터 한 단어씩 비교해줌
        for(int j = 0; j < wordSize; j++)
        {
            if(cur[j] != checkWord[j])
            {
                difCount++;
            }
        }
        //만약 한개의 단어만 다르다면 단어를 들고 함수 실행
        if(difCount == 1)
        {
            solve(checkWord, target, words, cnt+1);
        }
        //다음 단어들을 위해 빼두었던 단어를 다시 넣어줌
        words.push(checkWord);
        difCount = 0;
    }
}

int solution(string begin, string target, vector<string> words) {
    int answer = 0;
    queue<string> q;
    for(string s : words)
    {
        q.push(s);
    }
    wordSize = begin.size();
    solve(begin, target, q, 0);
    
    answer = changeCount;
    
    return answer;
}

출저

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