[programmers] 단어 변환

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

프로그래머스

 

---

< 단어 변환 >

 

문제 풀이 (Java)

import java.util.*;

class Solution {
	static class Word {
		String word;
		int cnt;

		public Word(String word, int cnt) {
			this.word = word;
			this.cnt = cnt;
		}
	}

	public int solution(String begin, String target, String[] words) {
		int answer = 0;

		Queue<Word> queue = new LinkedList<>();
		queue.add(new Word(begin, 0));

		boolean visited[] = new boolean[words.length];

		while (!queue.isEmpty()) {
			Word word = queue.poll();

			for (int i = 0; i < words.length; i++) {
				if (!visited[i]) {
					int temp = 0;
					for (int j = 0; j < words[i].length(); j++) {
						if (word.word.charAt(j) != words[i].charAt(j)) {
							temp += 1;
						}
					}
					if (temp == 1) {
						if (words[i].equals(target)) {
							answer = word.cnt + 1;
							break;
						}
						visited[i] = true;
						queue.add(new Word(words[i], word.cnt + 1));
					}
				}
			}
			if (answer > 0) {
				break;
			}
		}
		return answer;
	}
}

 

Queue에 begin 단어와 변환 횟수 0을 저장한 후 Queue가 빌 때까지 다음 과정을 반복한다.

 

1. Queue poll

2. words를 탐색하며 아직 거친 단어가 아니고 현재 단어와 비교했을 때 한 개의 알파벳만 차이 난다면 방문 표시 및 Queue에 추가한다. 이때, 이 단어가 target 단어와 일치한다면 answer을 업데이트하고 종료한다.

 

최종 answer을 반환한다. 

---

---

 

출처: 프로그래머스 코딩 테스트 연습, 
https://school.programmers.co.kr/learn/challenges