[Lv.3] 단어 변환 [프로그래머스_코딩테스트] [BFS] [30분]

🔍 문제 요약

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

프로그래머스

begin이라는 단어에서 target으로 변환을 시키려고 할 때 알파벳 하나씩을 바꿔서 words에 있는 단어들 중에서 옮겨가면서 target으로 바꾸려고 한다. 그렇게 했을때 최소의 단계를 거쳤을때의 횟수를 반환하는 문제. 못 바꾸는 경우 0 반환

🧠 나의 접근 방식과 시행착오

25분 정도에 푼 문제. 해당 문제는 생각외로 쉽게 풀었던 듯 하다. BFS는 Queue와 Visited를 활용하면 된다는 기준을 가지고 있어서인지 여러 문제를 풀다 보니 반복되는 패턴이 보이는 듯 하기도 하다. 일단 Queue<(string, int)>와 같은 구조를 짜서 begin을 먼저 집어 넣는다. 이때 int는 count를 가리키는 거라 0으로 시작을 한다. 그 후 while문에서 q를 하나씩 dequeue시키면서 돌면서 words에서 단어가 하나만 차이가 나는 지 체크하는 CompareString 함수를 호출한다. 그렇게 조건이 만족하는 경우 체크해서 방문했다는 표시로 bool 배열을 선언하고 각 words의 인덱스별로 방문했는지를 체크를 해서 다시 해당 word를 체크하지 않게 한다. (같은 단어를 차게 되면 계속 무한반복하게 동일한 단어를 가리키게 되기에) 그렇게 해서 결국 target 단어까지 도달을 하면 queue에 증가시켜왔던 count를 반환하면 되고 queue를 다 썼는데도 도달을 하지 못한 경우 0을 반환하면 된다.

using System.Collections.Generic;

public class Solution
{
    /// <summary>
    /// 단어 변환
    /// https://school.programmers.co.kr/learn/courses/30/lessons/43163
    /// </summary>
    public int solution(string begin, string target, string[] words)
    {
        // BFS를 활용해서 begin에서 target으로 단어를 변환하는데 걸리는 최단 방법 구하기
        Queue<(string, int)> q = new Queue<(string, int)>();
        bool[] visited = new bool[words.Length];
        q.Enqueue((begin, 0));
        
        while (q.Count > 0)
        {
            var current = q.Dequeue();
            var str = current.Item1;
            int count = current.Item2;

            if (str.Equals(target)) return count;

            for (int i = 0; i < words.Length; i++)
            {
                string word = words[i];
                
                if (!visited[i] && CompareString(str, word))
                {
                    visited[i] = true;
                    q.Enqueue((word, count + 1));
                }
            }
        }
        
        return 0;
    }

    public bool CompareString(string current, string word)
    {
        int sameCount = 0;
        
        for (int i = 0; i < current.Length; i++)
        {
            if (word[i] == current[i])
            {
                sameCount++;
            }
        }

        return sameCount == current.Length - 1;
    }
}

✅ 풀이 코드

크게 피드백 들어온 부분은 없었고 CompareString에서 early return 하는 형식을 알려주었다. (단어가 길수록 해당 방향이 효율이 좋긴 하다)

public bool CompareString(string current, string word)
{
    int diffCount = 0;
    for (int i = 0; i < current.Length; i++)
    {
        if (current[i] != word[i])
        {
            diffCount++;
            if (diffCount > 1) return false;
        }
    }
    return diffCount == 1;
}

🔄 정리

BFS는 Queue와 Visited, 그리고 최단 시간이든 횟수 등을 구하는 것이라는 점을 잘 인식해서 패턴처럼 기억해두자.