[프로그래머스] 단어 변환 - BFS

BFS을 통해 쉽게 풀 수 있는 문제였습니다.

 

프로그래머스 단어 변환 문제

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

 

문제는

두 개의 단어 begin, target과 단어의 집합 words가 주어지고 규칙들을 활용해서 begin -> target으로 변환시키는 과정입니다.
여기서 규칙들을 지키면서 변환했을때, 가장 짧게 변환 시킬 수 있는 경로를 구하는 문제입니다.

 

우선 문제를 보고 가장 짧은 과정을 구하는 문제라고 하였기 때문에, BFS로 접근하여야겠다고 생각하였습니다.

 

여기서 핵심 규칙은 단 한 개의 알파벳만 바꿀 수 있다는 것이었습니다.

즉, BFS로 접근할 때 현재 문장에서 words의 단어 중 단 한 알파벳만 다른 단어를 찾아서 탐색을 실행하면 됬습니다.

 

그렇기 때문에, 우선 한 알파벳만 다른 경우를 찾는 함수를 작성하였습니다.

boolean isDiffer(String start, String dest) {
    int differCount = 0;

    for (int i = 0; i < start.length(); i++) {
        if (start.charAt(i) == dest.charAt(i)) continue;
        differCount++;
    }

    return differCount == 1; 
}

 

 

 

이제 이 메소드를 활용해 한 글자만 다른 경우를 추적하고 Queue에 넣어 꺼내면서 전체를 탐색하는 방식으로 BFS 함수를 작성하면 됩니다.

저는 여기서 변환한 과정의 수를 카운트하기 위해 Word 클래스를 만들어서 Queue에 저장하면서 수행하였습니다.

 

먼저 BFS를 도는 과정의 코드를 보도록 할게요.

public int search(String curWord, String target, String[] words) {
    Queue<Word> queue = new LinkedList<>();
    boolean[] visited = new boolean[words.length];
    queue.offer(new Word(curWord, 0));

    while (!queue.isEmpty()) {
        Word tempWord = queue.poll();

        for (int i = 0; i < words.length; i++) {
            if (isDiffer(tempWord.word, words[i]) && !visited[i]) {
                if (words[i].equals(target)) {
                    return tempWord.convertNumber+1;
                }
                visited[i] = true;
                queue.offer(new Word(words[i], tempWord.convertNumber+1));
            }
        }
    }

    return 0;
}

 

여기서 위에서 작성한 코드를 활용해 한 단어만 다르고 아직 방문하지 않은 경우 변환 과정의 수를 +1하고 Queue에 삽입하는 것을 알 수 있습니다.

 

이런 식으로 완전탐색을 수행하고 목적 단어를 찾았을 때, 변환 과정의 수를 return하면 됩니다.

 

전체 코드를 보면

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

class Word {
    String word;
    int convertNumber;

    Word(String word, int convertNumber) {
        this.word = word;
        this.convertNumber = convertNumber;
    }
}

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

        for (int i = 0; i < words.length; i++) {
            if (!target.equals(words[i])) continue;
            else {
                answer = search(begin, target, words);
                break;
            }
        }

        return answer;
    }
    
    int search(String curWord, String target, String[] words) {
        Queue<Word> queue = new LinkedList<>();
        boolean[] visited = new boolean[words.length];
        queue.offer(new Word(curWord, 0));

        while (!queue.isEmpty()) {
            Word tempWord = queue.poll();

            for (int i = 0; i < words.length; i++) {
                if (isDiffer(tempWord.word, words[i]) && !visited[i]) {
                    if (words[i].equals(target)) {
                        return tempWord.convertNumber+1;
                    }
                    visited[i] = true;
                    queue.offer(new Word(words[i], tempWord.convertNumber+1));
                }
            }
        }

        return 0;
    }

    boolean isDiffer(String start, String dest) {
        int differCount = 0;

        for (int i = 0; i < start.length(); i++) {
            if (start.charAt(i) == dest.charAt(i)) continue;
            differCount++;
        }

        return differCount == 1;
    }
}

 

이상 BFS을 이용해서 쉽게 풀 수 있는 문제였습니다.