[프로그래머스] 단어 변환

1) 문제

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

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

 

입출력 예

begin	target	words	return
hit	cog	hot, dot, dog, lot, log, cog	4
hit	cog	hot, dot, dog, lot, log	0

 

begin의 단어를 target으로 변경해야 하는데

words에 있는 단어로만 변경이 가능하고 한번에 한개의 알파벳만 바꿀 수 있다.

 

최소 몇 단계를 거쳐야 바꿀 수 있는지 return

 

*모든 단어의 길이는 같다.

 

2) 풀이

일단 begin의 단어를 words에 있는 단어와 비교해서 변경이 가능한지 확인하는 함수가 필요할 것으로 보인다.

그럼 한번에 한 개의 알파벳만 변경이 가능하므로 단어의 길이-1 만큼의 글자수가 같아야한다.

 

DFS의 경우

check 벡터에 확인한 단어를 표시하고 나머지 다른 단어들과 비교한다.

현재 단어에 나머지 단어가 연결되어있다고 생각하면 된다.

 

종료 조건 

현재 단어와 target이 동일하면 return

이 때 answer를 cnt와 비교하고 작은 값을 저장한다.

 

3) 코드

#include <string>
#include <vector>
#include <algorithm>

using namespace std;
int answer = 10000;
vector<int> checkingWord(50, 0);

//변환 가능한 지 판별하는 함수
bool checkChangeAvailable(string a, string b) {
    int cnt = 0;
    //string을 글자 하나씩 돌아가며 같은 글자 카운팅
    for (int i = 0; i < a.length(); i++) {
        if (a[i] == b[i]) cnt += 1;
    }
    //틀린 글자 수가 1개라면 변환 가능
    if (cnt == a.length() - 1)
        return true;
    else
        return false;
}

void dfs(vector<string> words, string currentWord, string target, int cnt) {
    //현재 단어의 인덱스 검색, checking 벡터에 넣기 위함
    int idx = find(words.begin(), words.end(), currentWord)-words.begin();
    //종료 조건 현재 단어와 target 단어가 같은 경우
    if (currentWord == target) {
        //cnt가 answer보다 작거나 같은 경우에만 answer에 cnt 저장
        answer = answer < cnt ? answer : cnt;
        return;
    }
    //현재 단어 확인 저장
    checkingWord[idx] = 1;
    
    //현재 단어와 나머지 단어를 비교
    for (int i = 0; i < words.size(); i++) {
        //이미 확인한 단어가 아니고 변환 가능하면 dfs
        if (checkingWord[i] == 0 && checkChangeAvailable(currentWord, words[i])) {
            dfs(words, words[i], target, cnt+1);         
        }
    }
    //return 전에 현재 단어 확인 복구
    checkingWord[idx] = 0;
    
}

int solution(string begin, string target, vector<string> words) {
    dfs(words, begin, target, 0);

    return answer != 10000 ? answer : 0;
}

 

3) 정리

check 벡터를 초기화하는 것을 깜빡해서 시간이 좀 걸렸다.

그 문제 말고는 딱히 특별한 문제는 아니었다.

최소값을 찾는 문제이기 때문에 answer값을 충분히 큰 값으로 설정해야한다.