[프로그래머스/Kotlin] 단어변환 (Lv. 3)

문제

두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다.

1. 한 번에 한 개의 알파벳만 바꿀 수 있습니다.
2. words에 있는 단어로만 변환할 수 있습니다.

 

예를 들어 begin이 "hit", target가 "cog", words가 ["hot","dot","dog","lot","log","cog"]라면 "hit" -> "hot" -> "dot" -> "dog" -> "cog"와 같이 4단계를 거쳐 변환할 수 있습니다.

두 개의 단어 begin, target과 단어의 집합 words가 매개변수로 주어질 때, 최소 몇 단계의 과정을 거쳐 begin을 target으로 변환할 수 있는지 return 하도록 solution 함수를 작성해주세요.

 

제한사항

• 각 단어는 알파벳 소문자로만 이루어져 있습니다.
• 각 단어의 길이는 3 이상 10 이하이며 모든 단어의 길이는 같습니다.
• words에는 3개 이상 50개 이하의 단어가 있으며 중복되는 단어는 없습니다.
• begin과 target은 같지 않습니다.
• 변환할 수 없는 경우에는 0를 return 합니다.

 

입출력 예

 

풀이 방법

1. 정답 변수에는 Integer의 최대값을 넣고, Words, visited, Target을 전역변수로 설정한다.

그리고 주어진 매개변수를 복사한다. visited는 방문 체크 배열로 false로 초기화한다.

var result = Integer.MAX_VALUE
lateinit var Words: Array<String>
lateinit var visited: Array<Boolean>
lateinit var Target: String

fun solution(begin: String, target: String, words: Array<String>): Int {

Words = words
visited = Array<Boolean>(Words.size, {false})
Target = target

 

2. begin 문자와 count(현재는 0)를 담아 dfs 함수를 실행한다.

dfs(begin, 0)

 

3. 만약 현재 매개변수로 들어온 begin이 우리가 찾고자하는 Target 값과 같다면 정답 변수인 result와 count를 비교해 더 큰 값을 result에 넣고 return 한다.

fun dfs(begin: String, count: Int){
    if(begin == Target){
        result = Math.min(result, count)
        return
    }

 

4. 만약 같지 않다면 아래의 코드를 시작한다.

Words의 길이만큼 반복문을 돌리며 방문했다면 continue하고, 방문하지 않았다면 매개변수로 들어온 begin과 Words의 i번째에 해당하는 값을 매개변수로 가지는 check 함수를 실행한다.

true라면 i번째에 해당하는 방문 처리를 하고 count+1을 한 뒤 dfs를 실행하고 후에 방문처리를 false로 바꾼다.

var len = Words.size
for(i in 0 until len){
    if(visited[i]) continue

    if(check(begin, Words[i])){
        visited[i] = true
        dfs(Words[i], count+1)
        visited[i] = false
    }
}

 

5. 주어진 current와 target 문자열을 하나씩 쪼개서 같은지 비교한다. 조건 '1. 한번에 한 개의 알파벳만 바꿀 수 있습니다.' 를 만족하기 위해서는 current와 target의 다른 문자는 1개만 존재해야한다. 만약 1개만 존재한다면 true를 그렇지 않다면 false를 반환한다.

fun check(current: String, target: String): Boolean {
    var cnt = 0
    for(i in 0 until current.length){
        if(current[i] != target[i]){
            cnt++
        }
    }
    return cnt==1
}

 

코드

import java.util.*

class Solution {
    var result = Integer.MAX_VALUE
    lateinit var Words: Array<String>
    lateinit var visited: Array<Boolean>
    lateinit var Target: String
    fun solution(begin: String, target: String, words: Array<String>): Int {
        var answer = 0
        
        Words = words
        visited = Array<Boolean>(Words.size, {false})
        Target = target
        
        dfs(begin, 0)
        
        if(result == Integer.MAX_VALUE){
            return 0
        }

        return result
    }
    
    fun dfs(begin: String, count: Int){
        if(begin == Target){
            result = Math.min(result, count)
            return
        }
        
        var len = Words.size
        for(i in 0 until len){
            if(visited[i]) continue
            
            if(check(begin, Words[i])){
                visited[i] = true
                dfs(Words[i], count+1)
                visited[i] = false
            }
        }
    }
    
    fun check(current: String, target: String): Boolean {
        var cnt = 0
        for(i in 0 until current.length){
            if(current[i] != target[i]){
                cnt++
            }
        }
        return cnt==1
    }
}

 

 

 

코딩테스트 연습 - 단어 변환 | 프로그래머스 스쿨 (programmers.co.kr)

프로그래머스