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

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

프로그래머스

1. 정답코드 및 핵심 아이디어, 유의사항

시작 단어에서 목표 단어로 변환하기까지의 최소 변환 횟수를 구하는 문제

- 주어진 단어들로만 변환할 수 있음

- 단어 내의 알파벳 중 단 하나만 다른 경우에만 변환할 수 있음

- 만약, 변환할 수 없는 경우 0을 리턴

 

최소 변환 횟수를 구하는 문제 : BFS 알고리즘 (너비 우선 탐색) 적용

+ 한번 변환했던 단어로는 다시 변환해도 의미가 없음

https://godgjwnsgur7.tistory.com/47

[Algorithm C#] BFS, DFS ( + Back Tracking )

주석 참조

    using System;
    using System.Collections.Generic;

    public class Solution
    {
        public class DataClass
        {
            public string word; // 현재단어
            public int count; // 누적변환횟수

            public DataClass(string word, int count)
            {
                this.word = word;
                this.count = count;
            }
        }

        public int solution(string begin, string target, string[] words)
        {
            var boolArray = new bool[words.Length]; // 방문배열
            var queue = new Queue<DataClass>(); // BFS Queue

            queue.Enqueue(new DataClass(begin, 0)); // 초기 값 세팅

            // BFS 탐색
            while (queue.Count > 0)
            {
                DataClass data = queue.Dequeue();

                for (int i = 0; i < words.Length; i++)
                {
                    // 이미 변환했던 단어거나 변환할 수 없는 경우
                    if (boolArray[i] || Function(words[i], data.word) == false)
                        continue;

                    // target으로 변환이 가능한 경우
                    if (target == words[i])
                        return data.count + 1;

                    // 변환이 가능한 단어를 찾은 경우 
                    boolArray[i] = true;
                    queue.Enqueue(new DataClass(words[i], data.count + 1));
                }
            }

            return 0;
        }

        // 변환이 가능한 두 단어인지 판단하는 메서드
        public bool Function(string s1, string s2)
        {
            int count = 0;
            for (int i = 0; i < s1.Length; i++)
                if (s1[i] != s2[i])
                    count++;

            return count == 1; // 변환 가능 조건
        }
    }