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

출처: 프로그래머스 코딩 테스트 연습
https://school.programmers.co.kr/learn/courses/30/lessons/43163

 

 

나의 풀이

public int solution(string begin, string target, string[] words) 
{
    if(!words.Contains(target)) return 0;

    int answer = int.MaxValue;
    bool[] visit = new bool[words.Length];
    DFS(0, begin, target, words, visit, ref answer);

    return answer == int.MaxValue ? 0 : answer;
}

void DFS(int n, string cur, string target, string[] words, bool[] visit, ref int answer)
{
    if(cur == target)
    {
        if(n < answer)
            answer = n;
        return;
    }

    for(int i = 0; i < words.Length; ++i)
    {
        if(visit[i]) continue;
        if(DifferentCount(cur, words[i]) != 1) continue;

        visit[i] = true;
        DFS(n + 1, words[i], target, words, visit, ref answer);
        visit[i] = false;
    }
}

int DifferentCount(string strA, string strB)
{
    return Enumerable.Range(0, strA.Length).Count(i => strA[i] != strB[i]);
}

일반적인 DFS 문제.

변환하는 중 거치는 문자열을 다시 방문하는 경우는 무한루프를 돌게 돼서 필요는 없으니 visit 체크를 해줘야 한다.