[C#]프로그래머스/단어변환/DFS

 

using System.Collections.Generic;
using System.Linq;
 
public class Solution
{
    private int minCount = int.MaxValue;
    HashSet<string> usedWord = new HashSet<string>();
 
    public int solution(string begin, string target, string[] words)
    {
        //단어목록에 target이 없다면 바꿀 수 없다.
        if (words.Contains(target))
        {
            DFS(begin, target, 0, words);
 
            return minCount;
        }
        else
        {
            return 0;
        }
    }
 
    public void DFS(string currentWord, string target, int step, string[] words)
    {
        if (currentWord == target)
        {
            if (step < minCount)
                minCount = step;
 
            return;
        }
 
        usedWord.Add(currentWord);
 
        int minDifferenceCount = int.MaxValue;
        int nextIndex = 0;
 
        for (int i = 0; i < words.Length; i++)
        {
            //이미 쓴 단어는 제외
            if (usedWord.Contains(words[i]))
                continue;
 
            //현재 단어에서 알파벳 하나만 바뀌어야 한다.
            int differenceCount = currentWord.Zip(words[i], (a, b) => a == b ? 0 : 1).Sum();
 
            //target에 도달할 가능성이 가장 높은 것을 찾아서 nextIndex를 정한다. (가지치기)
            int differenceCountWithTarget = target.Zip(words[i], (a, b) => a == b ? 0 : 1).Sum();
 
            //알파벳 하나만 바뀌고, target과 알파벳이 다른 개수가 가장 적은 index를 갱신
            if (differenceCount == 1 && differenceCountWithTarget < minDifferenceCount)
            {
                minDifferenceCount = differenceCountWithTarget;
                nextIndex = i;
            }
        }
 
        DFS(words[nextIndex], target, ++step, words);
    }
}