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

1. 문제 풀이 아이디어

• 문자가 하나만 다른 문자열을 BFS로 찾으면 문제를 해결할 수 있다.

2. 나의 정답 코드

class Solution {
    public int solution(String begin, String target, String[] words) {
        int[] depth = new int[words.length];
        Queue<Integer> que = new ArrayDeque<>();
        for (int i = 0; i < words.length; i++) {
            if (isLinked(begin, words[i])) {
                depth[i]++;
                que.add(i);
            }
        }
        while (!que.isEmpty()) {
            int ci = que.poll();
            if (words[ci].equals(target)) {
                return depth[ci];
            }
            for (int i = 0; i < words.length; i++) {
                if (depth[i] > 0)
                    continue;
                if (isLinked(words[ci], words[i])) {
                    depth[i] = depth[ci] + 1;
                    que.add(i);
                }
            }
        }
        return 0;
    }

    private boolean isLinked(String wordA, String wordB) {
        int count = 0;
        for (int i = 0; i < wordA.length(); i++) {
            if (wordA.charAt(i) == wordB.charAt(i))
                continue;
            count++;
            if (count > 1) {
                return false;
            }
        }
        return true;
    }
}

3. 정리

• 깊이를 저장할 depth 배열과 문자열의 인덱스를 저장할 que를 정의한다.

• 먼저, begin과 한 글자만 다른 문자열을 찾아 que에 추가하고, 해당 인덱스의 depth 값을 1로 설정한다.

• que에서 가장 앞의 인덱스를 꺼내 그 인덱스의 문자열이 target과 같다면 해당 depth 값을 반환한다.

• 문자열 배열에서 depth가 0인(아직 방문하지 않은) 인덱스의 문자열 중 현재 인덱스의 문자열과 한 글자만 다른 경우, 그 인덱스의 depth 값을 현재 depth + 1로 설정하고 que에 추가한다.

• que가 빌 때까지 반복하고, while문을 빠져나오면 target이 없으므로 0을 반환한다.