프로그래머스 Level3)단어 변환

문제 설명

두 개의 단어 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

입출력 예 설명

예제 #1

문제에 나온 예와 같습니다.

예제 #2

target인 "cog"는 words 안에 없기 때문에 변환할 수 없습니다.

풀이

백준 풀다가 이거 푸니까 왜케 쉬움
미리 한글자씩 다른 거를 각각 인접 리스트에 추가해주고
그리고 그냥 bfs

import java.io.IOException;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;

public class Main {
	public static void main(String[] args) throws IOException {
		String begin = "hit";
		String target = "cog";
		String[] words = { "hot", "dot", "dog", "lot", "log", "cog" };
		int n = words.length;
		int[] check = new int[n];
		ArrayList<Integer>[] a = new ArrayList[n];
		for (int i = 0; i < n; i++) {
			a[i] = new ArrayList<>();
		}

		for (int i = 0; i < n; i++) {
			String s = words[i];

			for (int j = i + 1; j < n; j++) {
				int wrong = 0;
				for (int k = 0; k < s.length(); k++) {
					if (s.charAt(k) != words[j].charAt(k))
						wrong++;
				}
				if (wrong <= 1) {

					a[i].add(j);
					a[j].add(i);
				}
			}
		}

		int start = 0;
		Queue<Integer> q = new LinkedList<Integer>();
		for (int i = 0; i < n; i++) {
			int wrong = 0;
			for (int k = 0; k < begin.length(); k++) {
				if (begin.charAt(k) != words[i].charAt(k))
					wrong++;
			}
			if (wrong <= 1) {

				q.add(i);
				check[i] = 1;
			}
		}
		int ans=0;
		while (!q.isEmpty()) {
			int x = q.remove();
			if(target.equals(words[x]) )
				ans = check[x];
			for (int num : a[x]) {
				if (check[num] == 0) {
					q.add(num);
					check[num] = check[x]+1;
				}
			}
		}

		System.out.println(ans);
	}
}