[programmers] 단어 변환 (Java)

- 단어 변환

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

프로그래머스

 

- 접근 방법

BFS 탐색을 통해 문제를 해결하고자 한다.

1. begin 을 루트 노드로서 설정

2. "한 번에 한 개의 알파벳만 바꿀 수 있습니다." 규칙 1을 통해, 각 단어로 부터 한 개의 알파벳만 바뀐 것을 인접한 노드로 한다.

EX) 'hit' 과 'hot' 은 한 개의 알파벳만 바뀌었기 때문에 서로 간선으로 연결된다.

'dot' 은 'hot' 과는 간선으로 연결될 수 있지만, 'hit' 과는 간선으로 연결될 수 없다.

3. 간선으로 연결된 노드들을 탐색해 나가면서, target 과 동일한 단어가 완성하게 되면 성공이다.

 

 

- Java 코드

//https://school.programmers.co.kr/learn/courses/30/lessons/43163
//코딩테스트 연습 - 깊이/너비 우선 탐색(DFS/BFS) - 단어 변환

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

class Solution {

    class WordNode {
        String word;
        int steps;

        public WordNode (String word, int steps) {
            this.word = word;
            this.steps = steps;
        }
    }


    public int solution(String begin, String target, String[] words) {

        // # words 에 target 이 존재하는지 확인
        if (!Arrays.asList(words).contains(target)) {
            return 0;
        }

        Queue<WordNode> queue = new LinkedList<>();
        boolean[] visited = new boolean[words.length]; //노드 방문 여부 체크 배열

        queue.offer(new WordNode(begin, 0));

        while (!queue.isEmpty()) {
            //초기 설정
            WordNode current = queue.poll();
            String currentWord = current.word;
            int currentSteps = current.steps;

            //목표 단어에 도달한 경우 변환 단계 수 반환
            if (currentWord.equals(target)) {
                return currentSteps;
            }

            //아직 방문하지 않았고, 변환 가능한 단어
            for (int i = 0; i < words.length; i++) {
                if (!visited[i] && canConvert(currentWord, words[i])) {
                    visited[i] = true; //방문 처리
                    queue.offer(new WordNode(words[i], currentSteps + 1));
                }
            }
        }

        return 0; //목표 단어에 도달할 수 없는 경우
    }

    private boolean canConvert(String word1, String word2) {
        int diffCount = 0;
        for (int i = 0; i < word1.length(); i++) {
            if (word1.charAt(i) != word2.charAt(i)) {
                diffCount ++;
            }
            if (diffCount > 1) {
                return false;
            }
        }

        return diffCount == 1;
    }
}