<Lv.3> 단어 변환 (프로그래머스 : C#)

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

📕 문제 설명

두 단어 begin과 target이 주어지고 단어 배열 words가 주어질 때 begin -> target으로 변환할 때 가장 짧은 변환 횟수 반환하기

1. 한 번에 하나의 알파벳만 변환 가능
2. 주어진 words 배열 내의 단어로만 변환 가능

• Input
  begin, target, words
• Output
  가장 짧은 변환 횟수 (변환할 수 없으면 0 반환)

예제

풀이

DFS로 words 내의 단어로 변환될 수 있는 경우 계속 타고가면서 변환 횟수 세기 -> 최종적으로 변환 횟수 작은거 반환하기

(처음에 visited 안두고 하다가 계속 시간 초과나서 헤맸다.. 안두면 호출해준 애를 또 다시 봐서 상호참조 계속하는 식이라 시간적으로 엄청 손해본다!)

using System;
using System.Collections.Generic;
using System.Linq;

public class Solution {
    public int solution(string begin, string target, string[] words) {
        if (!words.Contains(target)) return 0;
        HashSet<string> visited = new HashSet<string>();
        int answer = GetLengthToMakeTarget(begin, target, 0, words, visited);
        return answer == 51 ? 0 : answer;
    }
    
    private int GetLengthToMakeTarget(string currWord, string target, int length, string[] words, HashSet<string> visited)
    {
        if (visited.Contains(currWord)) return 51;
        if (length > words.Length) return 51;
        if (currWord == target) return length;
        visited.Add(currWord);
        int returnLength = 51;
        
        for (int i = 0; i < currWord.Length; i++)
        {
            string before = currWord.Substring(0, i);
            string after = currWord.Substring(i + 1);
            for (int j = 0; j < 26; j++)
            {
                string newWord = before + (char) ('a' + j) + after;
                if (words.Contains(newWord))
                {
                    int calculatedLength = GetLengthToMakeTarget(newWord, target, length + 1, words, visited);
                    returnLength = Math.Min(returnLength, calculatedLength);
                }
            }
        }
        visited.Remove(currWord);
        
        return returnLength;
    }
}

결과

추가로 이건 시간 초과 안날때 visited말고 다른 시도를 하던 것이다. 재귀에서 매번 newWord 생성이 아니라 처음 1회만 만들어서 하나 문자 바꿔서 갈 수 있는 단어들 담는 adjDict 만들어두고 재귀에서 쓰는식이다. 재귀에서 매번 new word 안찾기에 같은 단어 봐야하는 경우 이득을 볼 것이라 생각했는데 오히려 시간도 오래 걸리고 + 1번에서 계속 막힌다.

using System;
using System.Collections.Generic;
using System.Linq;

public class Solution {
    public int solution(string begin, string target, string[] words) {
        if (!words.Contains(target)) return 0;
        
        int answer = 51;
        Dictionary<string, List<string>> adjDict = new Dictionary<string, List<string>>();
        for (int i = 0; i < words.Length; i++)
        {
            string currWord = words[i];
            adjDict[currWord] = new List<string>();
            for (int j = 0; j < currWord.Length; j++)
            {
                string before = currWord.Substring(0, j);
                string after = currWord.Substring(j + 1);
                for (int k = 0; k < 26; k++)
                {
                    string newWord = before + (char) ('a' + k) + after;
                    if (words.Contains(newWord))
                    {
                        adjDict[currWord].Add(newWord);
                    }
                }
            }
        }
        HashSet<string> visited = new HashSet<string>();
        
        if (!adjDict.TryGetValue(begin, out var adjList))
        {
            for (int j = 0; j < begin.Length; j++)
            {
                string before = begin.Substring(0, j);
                string after = begin.Substring(j + 1);
                for (int k = 0; k < 26; k++)
                {
                    string newWord = before + (char) ('a' + k) + after;
                    if (words.Contains(newWord))
                    {
                        answer = GetLengthToMakeTarget(newWord, target, 1, adjDict, visited);
                    }
                }
            }
        }
        else
        {
            foreach(string adjWord in adjList)
            {
                answer = GetLengthToMakeTarget(adjWord, target, 1, adjDict, visited);
            }
        }
        
        return answer == 51 ? 0 : answer;
    }
    
    private int GetLengthToMakeTarget(string currWord, string target, int length, Dictionary<string, List<string>> adjDict, HashSet<string> visited)
    {
        if (visited.Contains(currWord)) return 51;
        if (length > adjDict.Count) return 51;
        if (currWord == target) return length;
        int returnLength = 51;
        visited.Add(currWord);
        
        for (int i = 0; i < adjDict[currWord].Count; i++)
        {
            string newWord = adjDict[currWord][i];
            int calculatedLength = GetLengthToMakeTarget(newWord, target, length + 1, adjDict, visited);
            returnLength = Math.Min(returnLength, calculatedLength);
        }
        visited.Remove(currWord);
        
        return returnLength;
    }
}