[Kotlin/프로그래머스] 코딩테스트 연습 > 깊이/너비 우선 탐색(DFS/BFS) > 단어 변환

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
import java.util.*
class Solution {
    fun solution(begin: String, target: String, words: Array<String>): Int {
/*
1. 최소니까 bfs
2. isVisited를 두고 중복 방지
3. 큐에서 뽑은 item이 target이면 return
4. item에서 하나만 바꿔서 갈 수 있는 거를 visited하고 큐에 삽입
*/
        var answer = 0
        val queue: Queue<Pair<String, Int>> = LinkedList()
        val isVisited = Array<Boolean>(words.size) { false }
        queue.offer(begin to 0)
        while (queue.isNotEmpty()) {
            val item = queue.poll()
            if (item.first == target) {
                answer = item.second
                break
            }
            for (i in words.indices) {
                if (!isVisited[i] && isChangeWord(item.first, words[i])) {
                    isVisited[i] = true
                    queue.offer(words[i] to item.second + 1)
                }
            }
        }
        return answer
    }
    
    fun isChangeWord(origin: String, target: String): Boolean {
        var isDiff = 0
        for (i in origin.indices) {
            if (origin[i] != target[i]) isDiff++
        }
        return isDiff == 1
    }
}