프로그래머스: 단어 변환(DFS + String.Index)

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

프로그래머스

 

 

 

한 번에 한 개의 알파벳만 바꿀 수 있고 target으로 변환하는 가장 짧은 변환 과정을 찾는 문제이기 때문에 DFS로 접근했다.

전체적인 풀이 방법은 다음과 같다

1. 재귀함수를 이용하여 현재 단어(value)가 target과 같다면 종료한다 → DFS의 깊이가 정답 값
2. words 를 순회하면서 현재 단어(value)와 한 글자만 다른 글자를 찾는다
3. 한 글자만 다른 단어를 찾았다면, 해당 단어를 value로 두는 재귀함수를 호출한다.

 

첫 번째 시도(DFS + String.Index): core dumped 에러

import Foundation

func solution(_ begin:String, _ target:String, _ words:[String]) -> Int {
    var answer = Int.max // 최소값을 구하기 때문에 Int.max로 할당
    var strCount = begin.count // 단어 길이
    
    // DFS로 구현 (index: 변환 카운트, value: 현재 단어)
    func recur(index: Int, value: String) {
        if value == target { // 현재 단어와 타겟이 같으면 종료
            answer = min(answer, index) // 정답 값은 기존 변환 카운트와 현재 카운트 중 작은 값으로 할당
            return
        }
        
        // 모든 단어를 순회하면서 변환할 수 있는 단어(알파벳이 하나 차이나는) 찾기
        for word in words {
            var sameCount = 0 // 같은 문자 개수
            for i in 0..<strCount {
                let valueIndex = value.index(value.startIndex, offsetBy: i) // String.Index 타입으로 변환
                let wordIndex = word.index(word.startIndex, offsetBy: i) // String.Index 타입으로 변환
                if value[valueIndex] == word[wordIndex] { sameCount += 1 } // 해당 위치의 글자가 같으면 sameCount + 1
            }
            
            // 변환할 수 있는 단어라면 재귀 호출
            if sameCount + 1 == strCount {
                recur(index: index + 1, value: word)
            }
        }
    }
    
    recur(index: 0, value: begin)
    return answer == Int.max ? 0 : answer // answer이 기본값이었던 Int.max라면(target으로 변환하지 못했다면) 0 아니면 answer 리턴
}

core dumped 에러가 났다

현재 코드에서는 모든 단어를 순회하면서 현재 단어와 한글자만 다른 단어를 value로 두고 재귀호출을 한다

그러니 한 글자 차이 나는 단어끼리 계속 재귀호출을 하면서 종료되지 않아 발생하는 문제인 거 같다

 

예를 들어 words = [’dot’, ‘dog’]이고, 현재 value는 ‘dot’일 때를 보자

해당 함수에서 words를 순회하면서 value 값과 한 글자만 다른 단어를 찾는다

‘dot’, ‘dog’은 한 글자가 다르다.

따라서 if sameCount + 1 == strCount {} 조건문이 성립하기 때문에 재귀함수의 value가 dog으로 바뀌어 다시 호출된다

→ recur(index: index + 1, value: word) 이때 value = “dog”

value는 ‘dog’이 되어 다시 words의 모든 단어를 순회하면서 한 글자가 다른 단어를 찾는데

words 안에 있는 dot 또한 한 글자가 다르기 때문에 다시 value가 dot인 재귀함수가 호출되어 무한 반복되는 것이다

dot → dog → dot → dog → dot …

따라서 이미 변환했던 단어는 다시 변환하지 않게 visited 배열을 만들어 무한 반복되는 문제를 해결했다

 

두 번째 시도(DFS + String.Index)

import Foundation

func solution(_ begin:String, _ target:String, _ words:[String]) -> Int {
    var answer = Int.max       // 최소값을 구하기 때문에 Int.max로 할당
    var strCount = begin.count // 단어 길이
    var visited = Array(repeating: false, count: words.count) // 변환한 단어 구분
     // DFS로 구현 (index: 변환 카운트, value: 현재 단어)
    func recur(index: Int, value: String) {
        if value == target {  // 현재 단어와 타겟이 같으면 종료
            answer = min(answer, index) // 정답 값은 기존 변환 카운트와 현재 카운트 중 작은 값으로 할당
            return
        }
        
        // 모든 단어를 순회하면서 변환할 수 있는 단어(알파벳이 하나 차이나는) 찾기
        for i in 0..<words.count {
            let word = words[i] // 비교 문자
            var sameCount = 0 // 같은 문자 개수
            for j in 0..<strCount {
                let valueIndex = value.index(value.startIndex, offsetBy: i) // String.Index 타입으로 변환
                let wordIndex = word.index(word.startIndex, offsetBy: i) // String.Index 타입으로 변환
                if value[valueIndex] == word[wordIndex] { sameCount += 1 } // 해당 위치의 글자가 같으면 sameCount + 1
            }
            
             // 변환할 수 있는 단어이면서 변환하지 않았던 단어이면 재귀 호출
            if sameCount + 1 == strCount && !visited[i] {
                visited[i] = true
                recur(index: index + 1, value: word)
                visited[i] = false
            }
        }
    }
    
    recur(index: 0, value: begin)
    return answer == Int.max ? 0 : answer
}

 

 

 

 

추가) 문자열 요소의 접근: Subscript

String 타입에서 요소에 접근할 때는 배열과 달리 Int 타입이 아닌 String.Index 타입으로 접근해야 한다

for i in 0..<strCount {
    if value[i] == word[i] { sameCount += 1 } // Error: 'subscript(_:)' is unavailable: cannot subscript String with an Int, use a String.Index instead.
}

'subscript(_:)' is unavailable: cannot subscript String with an Int, use a String.Index instead.

String 타입은 Int로 접근하는 게 불가능하고 String.Index를 이용하여 접근할 수 있다

String 타입의 index(_:offsetBy:) 메서드를 통해 접근하려는 String.Index 타입을 구할 수 있다

 

위 코드에서는 아래와 같이 String.Index 타입을 구했다

 for j in 0..<strCount {
     let valueIndex = value.index(value.startIndex, offsetBy: i) // String.Index 타입으로 변환
     let wordIndex = word.index(word.startIndex, offsetBy: i) // String.Index 타입으로 변환
     if value[valueIndex] == word[wordIndex] { sameCount += 1 } // 해당 위치의 글자가 같으면 sameCount + 1
}

startIndex는 첫 번째 인덱스를 가리키며 해당 인덱스부터 i 만큼 떨어진 인덱스를 구할 수 있다

 

 

https://developer.apple.com/documentation/swift/string/index(_:offsetby:)

index(_:offsetBy:) | Apple Developer Documentation