주녘공부일지

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

CodingTest/Programmers Lv.3

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

주녘 2024. 3. 15. 16:31

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

 

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

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

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

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

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

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

 

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

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

https://godgjwnsgur7.tistory.com/47

 

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

1. BFS(Breadth First Search) - 너비 우선 탐색 최단 경로, 임의의 경로를 찾고 싶을 때, 등에 사용 - 큐(FIFO) 사용 // 큐를 이용 public void BFS(int index) { Node root = nodes[index]; Queue queue = new Queue(); queue.Enqueue(root

godgjwnsgur7.tistory.com

주석 참조

    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; // 변환 가능 조건
        }
    }