[Java] Lv.3 단어 변환

문제

 

프로그래머스

 

문제 풀이

1. 한 번 방문했던 단어는 더 이상 접근하지 않아도 된다.

2. 각 단어에 도달했었던 단계 (방문레벨)을 각각 기록한다.

 

우선, 각 위치의 words에 방문했었는지와 몇 번째로 방문했는지를 기록할 visited 배열을 하나 만들고

변환가능한 단어를 저장할 큐를 하나 생성한다.

다음으로 Begin에서 변환 가능한 모든 단어를 찾아서 큐에 담아내고 해당 단어의 index위치의 visited를 1로 저장한다.(1단계에 도달가능한 단어라는 의미)

 

이후 큐가 빌 때까지 확인을 거치는데

추출한 단어와 아직 방문레벨이 0인 단어를 비교해서 변환가능한지 확인한다.

변환가능할 경우 큐에 집어넣고 추출한 단어의 방문레벨의 +1 한 값을 visited에 기록해준다.

(이런 식으로 처리하면 begin에서 해당 단어에 도달하기 위한 방문단계가 visited에 기록되어 간다.)

그러다가 추출한 단어가 target과 같을 때 해당 단어의 vistited 값을 반환하고 종료한다.

 

큐가 비었는데도 결과가 반환되지 않았다면 변환 불가능한 단어로 생각하고 0을 반환한다.

자바 코드

import java.util.*;

class Solution {
    public int solution(String begin, String target, String[] words) {
        // 특정 word에 방문했는지와 몇 번째로 방문했는 지, 방문레벨를 기록하기 위한 배열
        int[] visited = new int[words.length];
        Queue<Integer> queue = new LinkedList<>();

        // 처음 begin에서 변환 가능한 단어들을 찾는다.
        // 찾은 단어의 인덱스를 큐에 담고 방문레벨을 +1해준다.
        for ( int i = 0; i < words.length; i++ ) {
            if ( visited[i] == 0 && Diff(begin, words[i]) ) {
                queue.offer(i);
                visited[i] = 1;
            }
        }

        // 큐가 빌때까지 반복
        while ( !queue.isEmpty() ) {
            // 큐에서 현재 변환가능한 단어의 인덱스를 하나 추출한다.
            int curIdx = queue.poll();
            // 추출한 인덱스의 위치의 단어
            String curStr = words[curIdx];

            // 추출한 단어가 원하는 target이면 해당 위치의 방문레벨을 출력하고 종료
            if ( curStr.equals(target) )
                return visited[curIdx];

            // 아직 방문하지 않은 단어와 현재 추출한 단어를 비교하여 변환가능한지 확인
            // 변환 가능하다면 추출한 단어의 방문레벨의 +1 만큼 방문레벨을 기록해준다.
            for ( int i = 0; i < words.length; i++ ) {
                if ( visited[i] == 0 && Diff( curStr, words[i] ) ) {
                    queue.offer(i);
                    visited[i] = visited[curIdx] + 1;
                }
            }
        }

        return 0;
    }
    
    // 두 단어의 다른 점을 확인할 메소드
    public boolean Diff(String word1, String word2){
        int diffCnt = 0;
        // 한 자리 한 자리 바교하여 다른지 확인
        for(int i = 0; i < word1.length(); i++){
            // 같은 자리의 단어가 다르면 카운트 +1
            if(word1.charAt(i) != word2.charAt(i))
                diffCnt++;
            
            // 카운트가 2개 이상이면 바꿀 수 없으므로 false
            if(diffCnt > 1)
                return false;
        }
        
        // 다른 단어가 1개면 true 반환
        return diffCnt == 1;
    }
}