[문제] 프로그래머스 레벨 3: 단어 변환

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

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

내 풀이

1. BFS

import java.util.LinkedList;
import java.util.Queue;

public class PG_43163 {
	
	public static int solution(String begin, String target, String[] words) {
		// 1. target이 words 배열안에 있는지 검사 후 없으면 0 반환
		boolean flag = false;
		int idx = -1;	// words 배열에서 target의 위치

		for (int i = 0; i < words.length; i++) {
			String s = words[i];
			if (s.equals(target)) {
				flag = true;
				idx = i;
				break;
			}
		}
		if (!flag)
			return 0;

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

//		BFS
		Queue<int[]> q = new LinkedList<>();
		q.add(new int[] { -1, 0 }); // -1 : start, 0: cnt (바꾸는 만큼 카운트)

		while (!q.isEmpty()) {
			int[] curr = q.poll();
			int cnt = curr[1];
			String s = null;
			if (curr[0] == -1) {
				s = begin;
			} else {
				s = words[curr[0]];
			}

			for (int i = 0; i < len; i++) {
				// 아직 방문하지 않은 단어와 현재 단어와 알파벳 차이가 1이라면,
				if (!visited[i] && different(s, words[i]) == 1) {
					visited[i] = true;
					q.add(new int[] { i, cnt + 1 });
				}
			}

			if (visited[idx]) {	// 타겟에 방문하는 순간 종료
				return cnt + 1;
			}
		}

		return 0;
	}

	// 현재 문자열이랑 바꿀 문자열이랑 차이가 얼마나 나는지 확인하는 함수
	static int different(String str, String change) {
		int ans = 0;
		for (int i = 0; i < str.length(); i++) {
			char cB = str.charAt(i);
			char cT = change.charAt(i);
			if (cB != cT)
				ans++;
		}
		return ans;
	}

}