[Programmers 프로그래머스] 43163 단어 변환 (JAVA)

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

코딩테스트 연습 - 단어 변환

문제 설명

두 개의 단어 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 합니다.

입출력 예

begin	target	words	return
"hit"	"cog"	["hot", "dot", "dog", "lot", "log", "cog"]	4
"hit"	"cog"	["hot", "dot", "dog", "lot", "log"]	0

 

BFS를 활용하여 문제를 해결했다.

Point라는 클래스를 두고, 단어와 횟수를 저장할 수 있도록 했다.

기본적으로 BFS는 LinkedList를 활용을해서 문제를 해결하는데, 해당하는 Queue가 비면 끝내도록 while문을 돌게 된다.

words에 begin과 한개가 다른 단어를 Queue에 계속 넣어주고, target이 나오는 순간 종료를 하게 된다.

import java.util.LinkedList;

class Solution {
	private static class Point{
		String word;
		int cnt;
		public Point(String word, int cnt) {
			super();
			this.word = word;
			this.cnt = cnt;
		}
	}
    public static int solution(String begin, String target, String[] words) {
        int answer = 0;
        // word를 담아줄 Queue
        LinkedList<Point> que=new LinkedList<Point>();
        que.add(new Point(begin,0));
        if(!check(target,words)) {
        	que.poll();
        }
        //BFS 시작
        while(!que.isEmpty()) {
        	Point p =que.poll();
            // 찾고 있는 target이 나오면 종료
        	if(p.word.equals(target)) {
        		answer=p.cnt;
        		break;
        	}
            // queue에 있는 단어와 words에 있는 단어를 비교해 하나가 다르면 Queue에 넣어준다.
        	for (int i = 0; i < words.length; i++) {
        		int count=0;
				for (int j = 0; j < p.word.length(); j++) {
					if(words[i].charAt(j)==p.word.charAt(j)) {
						count++;
					}
				}
				if(p.word.length()-count==1) {
					que.add(new Point(words[i],p.cnt+1));
				}
			}
        }
        return answer;
    }
	private static boolean check(String target, String[] words) {
		for (int i = 0; i < words.length; i++) {
			if(target.equals(words[i])) {
				return true;
			}
		}
		return false;
	}
}