링크

단어 변환

문제 설명

두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다.

1. 한 번에 한 개의 알파벳만 바꿀 수 있습니다.
2. words에 있는 단어로만 변환할 수 있습니다.

예를 들어 begin이 "hit", target가 "cog", words가 ["hot","dot","dog","lot","log","cog"]라면 "hit" -> "hot" -> "dot" -> "dog" -> "cog"와 같이 4단계를 거쳐 변환할 수 있습니다.

두 개의 단어 begin, target과 단어의 집합 words가 매개변수로 주어질 때, 최소 몇 단계의 과정을 거쳐 begin을 target으로 변환할 수 있는지 return 하도록 solution 함수를 작성해주세요.

제한사항

• 각 단어는 알파벳 소문자로만 이루어져 있습니다.
• 각 단어의 길이는 3 이상 10 이하이며 모든 단어의 길이는 같습니다.
• words에는 3개 이상 50개 이하의 단어가 있으며 중복되는 단어는 없습니다.
• begin과 target은 같지 않습니다.
• 변환할 수 없는 경우에는 0를 return 합니다.

풀이

이 문제는 LEVEL3보다는 LEVEL2가 맞는것 같다.
BFS의 기본문제라고 생각된다.

문제가 최소 단계를 구하는 것이기에 Queue를 사용하였다.
또한, class에 비교할 String, count값을 넣어주었다.

그 다음은, q에서 str값을 빼내서 words에 있는 단어들끼리 한단어씩 비교해나가면 끝!
이 문제에서는 시간복잡도가 초과하지는 않지만 2번째 예제처럼 이제 값이 0이될수도 있기에 visited를 넣어주었다.

Code

import java.util.*;

class Point
{
    String str;
    int count;
    
    Point(String str, int count)
    {
        this.str=str;
        this.count=count;
    }
}

class Solution {
    static boolean visited[];
    static Queue<Point> q=new LinkedList<>();
    static int answer=0;
    public int solution(String begin, String target, String[] words) {
        visited=new boolean[words.length];
        BFS(begin, target, words);
        return answer;
    }
    
    public static void BFS(String begin, String target, String[] words)
    {
        q.add(new Point(begin, 0));
        
        while(!q.isEmpty())
        {
            Point po=q.poll();
            String nowstr=po.str;
            int nowcount=po.count;
            
            if(nowstr.equals(target))
            {
                answer=nowcount;
                return;
            }
            
            for(int i=0; i<words.length; i++)
            {
                String tempstr=words[i];
                int count=0;
                for(int j=0; j<tempstr.length(); j++)
                {
                    if(nowstr.charAt(j)!=tempstr.charAt(j))
                        count++;
                    if(count==2)
                        break;
                }
                if(count==1 && !visited[i])
                {   
                    visited[i]=true;
                    q.add(new Point(words[i], nowcount+1));
                }
            }
        }
    }
}