[C#] 단어 변환

프로그래머스 문제

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

풀이 후기

1. 분석

AI추천으로 돌렸는데 방금 푼 가장 먼 노트랑 비슷한 문제인 느낌. 문제 분류에 스포도 되어있으니 똑같은 BFS로 풀었다. 살짝 다른 점은 엣지가 제공되지 않기 때문에 직접 판단해서 넣어줘야 한다는 점.

2. 엣지

단어의 한 글자만 바꿀 수 있다. -> 한 글자가 다른 단어로 이동 가능하다. 로 바꿔 말할 수 있다. 좋은 방법이 안떠올라서 for문 돌려서 단어들의 차이가 1개만 나게되면 엣지로 이어버리기로 했다. 근데 굳이 그래프를 열심히 만들지 않아도 배열 순회하면서 검색해도 괜찮을 것 같다.

3. 실행 결과

4. 코드

using System;
using System.Collections.Generic;

public class Solution {
    
    public class Word{
        public List<Word> edges = new List<Word>();
        public int index;
        public string content;
        public int count = 0;
        public bool isUsed = false;
        
        public Word(int i, string c){
            index = i;
            content = c;
        }
        
        public void AddEdge(Word w){
            edges.Add(w);
        }
    }
    
    public int solution(string begin, string target, string[] words) {
        int len = words.Length;
        Word[] wordArray = new Word[len + 1];
        
        for(int i = 0; i < len; i++){
            wordArray[i] = new Word(i, words[i]);
        }
        
        var beginWord = new Word(len, begin);
        beginWord.isUsed = true;
        wordArray[len] = beginWord;
        
        for(int i = 0; i < len + 1; i++){
            for(int loop = i; loop < len + 1; loop++){
                var a = wordArray[i].content;
                var b = wordArray[loop].content;
                int max = a.Length;
                int like = max;

                for(int n = 0; n < a.Length; n++){
                    if(a[n] != b[n]){
                        like--;
                    }
                }
                
                if(like == max - 1){
                    wordArray[i].AddEdge(wordArray[loop]);
                    wordArray[loop].AddEdge(wordArray[i]);
                }
            }
        }
        
        Queue<Word> nextWord = new Queue<Word>();
        nextWord.Enqueue(beginWord);
        
        while(nextWord.Count > 0){
            var outWord = nextWord.Dequeue();
            var count = outWord.count + 1;
            
            foreach(var e in outWord.edges){
                if(e.content.Equals(target)){
                    return count;
                }
                
                if(!e.isUsed){
                    e.isUsed = true;
                    e.count = count;
                    nextWord.Enqueue(e);
                }
            }
        }
        
        return 0;
    }
}