[알고리즘] 프로그래머스 단어 변환 -dfs, bfs-

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

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

프로그래머스 LEVEL3 단어 변환 문제를 풀어봤습니다.

bfs 를 사용해서 풀이했습니다.

한 단어는 한 글자만 변경이 가능한 경우 변경할 수 변환할 수 있습니다. (탐색 조건)

 

1. 큐에 시작 단어를 넣습니다.

2. 단어들을(words) 불러오고 이미 사용한 단어가 아닌 경우 현재 단어와 한글자씩 비교하고 변환이 가능한 경우 해당 글자를 큐에 추가하고 방문처리 해줍니다.(isConvert())

이때 몇번변환했는지 알 수 있게 Node 클래스의 cnt를 증가시켜 큐에 추가해줍니다.

 

 

 

[Java]

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

class Solution {

    // 현재단어에서 단어 변경 하나만 할 수 있는 경우만 변환 가능
    public static boolean isConvert(String word, String convertWord) {
        int count = 0;
        for (int i = 0; i < word.length(); i++) {
            if (word.charAt(i) != convertWord.charAt(i)) {
                count++;
            }
            if (count > 1) {
                return false;
            }
        }
        return true;
    }

    public int solution(String begin, String target, String[] words) {
        int answer = 0;
        boolean[] isVisited = new boolean[words.length];
        List<String> wordList = Arrays.asList(words);
        if (!wordList.contains(target)) { // target 단어 안가지고 있는 경우
            return 0;
        }

        //bfs
        Queue<Word> queue = new LinkedList<>();
        queue.offer(new Word(begin, 0));
        while (!queue.isEmpty()) {
            Word currentWord = queue.poll();
            if (currentWord.word.equals(target)) {
                answer = currentWord.cnt;
                break;
            }
            for (int i = 0; i < words.length; i++) {
                if (!isVisited[i] && isConvert(currentWord.word, words[i])) {
                    isVisited[i] = true;
                    queue.offer(new Word(words[i], currentWord.cnt + 1));
                }
            }
        }
        return answer;
    }

    static class Word {
        String word; // 단어
        int cnt; // 변경한 횟수

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

 

 

[Kotlin]

import java.util.*

class Solution {

    fun solution(begin: String, target: String, words: Array<String>): Int {
        var answer = 0
        val isVisited = BooleanArray(words.size)
        val wordList = Arrays.asList(*words)
        if (!wordList.contains(target)) { // target 단어 안가지고 있는 경우
            return 0
        }
        val queue = LinkedList<Word>()
        queue.offer(Word(begin, 0))

        while (!queue.isEmpty()) {
            with(queue.poll()) {
                if (this.word == target) {
                    answer = this.cnt
                    return answer
                }
                for (i in words.indices) {
                    if (!isVisited[i] && isConvert(this.word, words[i])) {
                        isVisited[i] = true
                        queue.offer(Word(words[i], this.cnt + 1))
                    }
                }
            }
        }
        return answer
    }

    data class Word(var word: String, var cnt: Int)

    companion object {
        fun isConvert(word: String, convertWord: String): Boolean {
            var count = 0
            for (i in 0 until word.length) {
                if (word[i] != convertWord[i]) {
                    count++
                }
                if (count > 1) {
                    return false
                }
            }
            return true
        }
    }
}

 

 

https://github.com/mtjin/algorithm_practice/tree/master/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4%20%EB%8B%A8%EC%96%B4%20%EB%B3%80%ED%99%98%20-bfs%2C%20dfs-

mtjin/algorithm_practice

 

감사합니다.!!