[Java] 프로그래머스_43163 : 단어 변환

너비 우선 탐색(BFS)

단어 변환 - Level3

 

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

프로그래머스

 

 

 

 

풀이

import java.util.*;

class Solution {
    
    // 두 단어가 한 글자만 차이나는지 확인하는 함수
    // 두 문자열을 문자 배열로 변환하여 각 위치에서의 문자를 비교하고, 차이가 1인 경우 true를 반환
    private boolean isConvertable(String beginStr, String targetStr) {
        char[] beginStrArr = beginStr.toCharArray();
        char[] targetStrArr = targetStr.toCharArray();
        
        int diff = 0;
        for (int i = 0; i < beginStrArr.length; i++) {
            if (beginStrArr[i] != targetStrArr[i]) diff++;
        }
        return diff == 1;
    }
    
    // word는 현재 단어를, step은 현재까지의 변환 과정 단계
    private static class State {
        public final String word;
        public final int step;
        
        private State(String word, int step) {
            this.word = word;
            this.step = step;
        }
    }
    
    public int solution(String begin, String target, String[] words) {
        boolean[] isVisited = new boolean[words.length];
        
        Queue<State> q = new LinkedList<>();
        q.add(new State(begin, 0));
        
        while (!q.isEmpty()) {
            State state = q.poll();
            
            if (state.word.equals(target)) {
                return state.step;
            }
            
            for (int i = 0; i < words.length; i++) {
                String next = words[i];
                
                // 상태 전이 검사 및 상태 전이
                if (!isConvertable(state.word, next)) {
                    continue;
                }
                
                if (isVisited[i]) {
                    continue;
                }
                
                isVisited[i] = true;
                q.add(new State(next, state.step + 1));
            }
        }
        return 0;
    }
}

 

BFS 알고리즘을 사용하여 최소 변환 과정을 찾는다. 큐(q)를 이용하여 탐색을 진행하며, 현재 단어에서 가능한 다음 단어를 찾아 큐에 추가한다. 변환 가능한 단어인 경우에만 탐색이 진행되고, 이미 방문한 단어는 무시된다. 목표 단어(target)에 도달하면 현재까지의 변환 단계를 반환하고 종료한다.

 

 

두 단어가 다르게 가지고 있는 문자를 모두 세기보다 다른 문자가 2개 이상이면 바로 변환할 수 없다고 반환하는 것이 효율적이다.

 

 

1. 상태 정의

BFS 문제는 대부분 초기 상태에서 목표 상태까지 도달하는 최단 경로 길이를 찾아야 한다.

여기서는 단어를 변환하는 횟수가 이에 해당한다. 이 횟수는 상태와 함게 횟수를 세어 쉽게 구할 수 있다.

하나의 상태인 단어에 횟수를 포함하여 State를 작성했다.

변환 횟수 step은 정답을 구하고자 추적하는 변수일 뿐, 상태 변수는 아니다.

private static class State {
    public final String word;
    public final int step;

    private State(String word, int step) {
        this.word = word;
        this.step = step;
    }
}

 

2. 방문 검사 배열

BFS를 위해 solution() 메서드에서 방문 검사 배열 isVisited를 선언했다.

이 배열은 변환 가능한 단어의 배열인 words에서 각 인덱스의 단어가 방문된 단어인지 나타낸다.

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

 

3. 초기 상태

BFS에서 사용되는 큐를 선언하고 초기 상태를 넣어준다. 초기 상태의 단어는 begin이며, 초기 단어에서 begin까지 변환 횟수가 0이기 때문에 step은 0으로 시작한다.

Queue<State> q = new LinkedList<>();
q.add(new State(begin, 0));

 

4. 탐색 진행

탐색 공간에 있는 상태를 순회하며 검사한다.

while (!q.isEmpty()) {
	State state = q.poll();
}

 

5. 현재 상태 처리

받아 온 상태에 대한 검사로, 정답을 검사한다. 해당 상태에 있는 단어가 target과 같으면 정답 상태에 도달한 것이므로 이때까지 센 변환 횟수를 반환한다.

if (state.word.equals(target)) {
	return state.step;
}

 

6. 전이 상태 생성

정답이 아니라면 단어를 변환시켜 상태 전이를 수행한다. words 에 있는 모든 단어를 순회하며 전이할 수 있는 단어를 골라낸다.

for (int i = 0; i < words.length; i++) {
	String next = words[i];
    
    // 상태 전이 검사 및 상태 전이
}

 

7. 유효성 검사

유효성 검사에서는 단어 next가 현재 상태에서 전이될 수 있는지 판단한다. 이는 isConvertable() 메서드를 이용한다.

if (!isConvertable(state.word, next)) {
	continue;
}

 

8. 중복 검사

배열 isVisited를 이용하여 중복 검사를 했다.

if (isVisited[i]) {
	continue;
}

 

9. 방문 처리 & 상태 전이

이렇게 검사를 통과한 상태는 전이될 수 있는 상태로, 방문 처리를 하고 탐색 공간에 추가한다.

isVisited[i] = true;
q.add(new State(next, state.step + 1));

 

모든 탐색 공간을 탐색했는데 정답 상태를 방문하지 못했다면 이는 단어를 변환할 수 있는 방법이 없는 것이다.

이 경우 0을 반환하도록 했다.

return 0;

 

 

 

해당 문제를 통해 BFS에 대해서 새롭게 공부하게 되었다. 앞으로 더 연습해 나가야겠다!