단어 변환 : BFS (Level3)

이번문제는 처음에 생각보다 접근 방식은 좋았다고 생각한다.

 

다만 오랜만에 BFS 관련 문제를 풀다보니, 헷갈리는 부분에 있어서 오래걸렸다.

 

이 문제를 BFS라고 판단한 이유는 최단경로를 구하는것이기 때문이다.

 

우선, 각각의 글자를 노드라고 생각하고, 접근 가능한(한글자 차이나는 값)노드를 연결시켜, 연결리스트 형태를 만들었다.

 

List<List<Integer>> list = new ArrayList<>();

list.get(0) = [1,3]

list.get(1) = [0,2,3]

list.get(2) = [1,4,5]

list.get(3) = [0,1,4]

list.get(4) = [2,3,5]

list.get(5) = [2,4]

 

추가로, 각각의 노드의 방문상태를 나타내는 visited[], 각각의 노드의 거리를 나타내는 resultArr[]를 만들었다.

 

위처럼 BFS를 구현하기 위해, 연결리스트/visited/resultArr가 필요하다.

 

핵심은 BFS이므로 설명을 해보도록하겠다. 먼저 너비우선의 정답은 0 > 1,3 > 2,4 > 5이다.

 

visited = [T,T,T,T,T,T] 

resultArr = [1,2,3,2,3,4] ---> 중요!!! 그전값의 +1을 해야한다. 

queue = 0,1,3,2,4,5 ---> 연결된 노드를 모두 offer 하나씩 remove하면서 이전값에 +1

 

BFS가 위와 같이 동작되면 된다.

추가로 주의 할점은 시작노드가 0번이 아닌 다른 숫자 일 수도 있다. 또 찾는문자가 마지막이 아닐 수도 있다는 점을 고려해야한다.

 

 

 

import java.util.*;

class Solution {

	public boolean[] visited;
	public int[] resultArr;

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

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

		// 연결리스트 초기화
		List<List<Integer>> list = new ArrayList<>();
		for (int i = 0; i < words.length; i++) {
			list.add(new ArrayList<Integer>());
		}

		// 연결리스트 만들기
		for (int i = 0; i < words.length; i++) {
			for (int j = 0; j < words.length; j++) {
				if (i != j && checkString(words[i], words[j])) { // 자기자신을 제외한 1글자 차이나는 것들 넣기
					list.get(i).add(j);
				}
			}
		}

		// target index
		int targetIndex = -1; // 찾고자 하는 값의 위치까지만 횟수를 구하면 된다.
		for (int i = 0; i < words.length; i++) {
			if (target.equals(words[i])) {
				targetIndex = i;
			}
		}
		
		if(targetIndex == -1) { // 결과값이 없다면
			return 0;
		}

		// 시작문자와 1글자 차이나는 즉, 시작 가능한 글자 인덱스 구하기
		List<Integer> startList = new ArrayList<>();
		for (int i = 0; i < words.length; i++) {
			if (checkString(begin, words[i])) {
				startList.add(i);
			}
		}

		for (int s : startList) { // 시작가능한 지점에서의 bfs로 가장 작은것을 구하자
			bfs(s, list);
			answer = Math.min(answer, resultArr[targetIndex]);

			visited = new boolean[words.length]; // 새로운 시작점부터 이므로 초기화
			resultArr = new int[words.length];
		}

		return answer;
	}

	public void bfs(int s, List<List<Integer>> list) {
		Queue<Integer> q = new LinkedList<>();
		q.offer(s);
		visited[s] = true;
		resultArr[s] = 1;

		while (!q.isEmpty()) {
			int now = q.remove();

			List<Integer> cList = list.get(now);
			for (int c : cList) {
				if (visited[c] == false) {
					visited[c] = true;
					q.offer(c);
					resultArr[c] = resultArr[now] + 1; // (증요!!! : 그전꺼의 +1을 한다) 
				}
			}
		}
	}

	// 틀린 문자의 갯수가 1일때 true
	public boolean checkString(String a, String b) {
		int count = 0;
		for (int i = 0; i < a.length(); i++) {
			if (a.charAt(i) != b.charAt(i)) { // char비교는 등호
				count++;
			}
		}
		return count == 1 ? true : false;
	}
}