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

문제

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

접근 방법

DFS로 재귀 + 백트래킹

• 매개변수 : 현재 단어, 카운트
• 종료 조건 : 현재 단어와 타겟 단어가 같을 때
• 방문하지 않고, 두 문자열이 1문자만 다를 때 -> Dfs 호출

풀이

#include <string>
#include <vector>
#include <iostream>
#include <algorithm>
#include <queue>

using namespace std;

int answer = 50;
bool visited[50];

bool CanChange(string a, string b)
{
    int cnt = 0;
    for(int i=0; i<a.length(); i++)
    {
        if (a[i] != b[i]) cnt++;
    }
    
    return (cnt == 1);
}

void Dfs(string current, int cnt, string &target, vector<string> &words)
{
    // 변환 끝
    if (current == target)
    {
        // 최솟값 갱신
        answer = min(answer, cnt);
        return;
    }
    
    // 최솟값 아닌 경우 탐색 그만 
    if (cnt > answer)
    {
        return;
    }
    
    for(int i=0; i<words.size(); i++)
    {
        if (!visited[i] && CanChange(words[i], current))
        {
            visited[i] = true;
            Dfs(words[i], cnt+1, target, words);
            visited[i] = false; // 백트래킹
        }

    }
}


int solution(string begin, string target, vector<string> words) {
    
    Dfs(begin, 0, target, words);
    
    if (answer == 50) answer = 0;
    
    return answer;
}

정리

백트래킹 더 연습해야겠다.

참고

https://velog.io/@euneun/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-%EB%8B%A8%EC%96%B4-%EB%B3%80%ED%99%98BFSDFS-C-v5lnyekn