[프로그래머스] 단어 변환

https://programmers.co.kr/learn/courses/30/lessons/43163?language=swift# 

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

 

딱 하나만 문자가 다를 경우 변경해줄 수 있으며, 이를 이용해서 원하는 값으로 최소한으로 이동하려는 문제.

이동한 다음 원소의 이동 가능한 선택지를 봐야하는 것이기에 DFS로 풀어줘야 한다. 

 

여기까지는 괜찮았는데.... 결론적으로 1문제만 풀리지 않더라. 

기존 풀이는 다음과 같다.

 

1. 특정 문자열과 1개만 차이나는 원소들을 리스트를 구한다 (similarity)

2. 1번의 결과 배열이 곧 다음으로 이동 가능한 원소들이기에 이를 기준으로 돌았다. 

3. 방문하지 않았고, 이동 가능한 원소들중 target을 가지고 있지 않은 경우에 대해서만 봐준다. 

    3-1. 도달한 배열 저장을 위해 result에 붙여준다. 

4. result를 모은 res를 기준으로하여 가장 최소 작은 배열의 길이를 리턴한다.

5. 마지막 이동 즉, target으로 이동하는 것은 못세줬기에 전부 + 1 해준다. 

 

// 실패
func solution(_ begin:String, _ target:String, _ words:[String]) -> Int {
    //DFS
    if !words.contains(target) { return 0 }
    
    var answer = Int.max
    var visited = Array(repeating: false, count: words.count+1)
    var result = [String]()
    var visitNext = [String]()
    var res = [[String]]()
    visitNext.append(begin)

    func DFS(_ arr: [String], _ start: String) -> Int {
        if start == target {
            return result.count
        }
        var next = visitNext.removeLast()
        
        for (v,i) in similarity(arr,next) {            
            if !visited[i] && !similarity(arr,next).map {$0.0}.contains(target) {
                visited[i] = true
                visitNext.append(v)
                result.append(v)
                DFS(arr,v)
                continue                
            } 
        }
        res.append(result)
        var low = res.map {$0.count}.min()!
        
        return answer > low ? low + 1 : answer + 1
    }
    answer = DFS(words,begin)
    return answer
}


func similarity(_ array: [String], _ word: String) -> [(String,Int)] {
    var w = word.map {String($0)}
    var res = [(String,Int)]()
    var arr = array.map {$0.map {String($0)}}
    
    for (i,a) in arr.enumerated() {
        var count = 0
        for j in 0..<a.count {
            if a[j] == w[j] {
                 count += 1
            }
        }
        if count == 2 {
            res.append((array[i],i))
        }
    }
    return res
}

 

하지만..?

 

 

테케 3만 통과하지 못했다...

질문들을 보니 "AAG" "AFA"의 경우처럼 중복되는 때를 고려하라고 했으나, 기존에 similarity를 보면 각 원소들 끼리 비교해서 중복 문제도 해결한 것을 알 수 있다. 

 

다만 확인해보니 주어진 words의 순서에 영향을 받도록 코드를 짠 것 같아서 추가 수정이 필요할 듯 하다.

 

그렇게 계속 헤매고 헤매다가 아래 풀이를 찾게 되었다.

(https://blog.naver.com/PostView.nhn?blogId=gustn3964&logNo=222138194056)

import Foundation

func solution(_ begin:String, _ target:String, _ words:[String]) -> Int {
    var visited = Array(repeating: false, count: words.count)
    var ans = Int.max
    
    func DFS(_ start: String, _ cnt: Int) {
        if start == target {
            ans = min(ans,cnt)
            return 
        }
        
        for i in 0..<words.count {
            if !visited[i] && zip(start, words[i]).filter {$0 != $1}.count == 1 {
                visited[i] = true
                DFS(words[i], cnt + 1)
                visited[i] = false
            }
        }
    }
    
    DFS(begin,0)
    return ans == Int.max ? 0 : ans
}

import Foundation

func solution(_ begin:String, _ target:String, _ words:[String]) -> Int {
    // 원소 방문 여부를 체크해 줄 배열 
    var visited = Array(repeating: false, count: words.count)
    // 최종 step 수 (아무리 커도 배열의 크기를 넘을 순 없음)
    var step = Int.max
    
    func DFS(_ start: String, _ depth: Int) {
        // 1. 종료 조건 (현재 원소가 목표 원소일 경우)
        if start == target {
            // 현재 경로와 이전 경로 중 최솟값을 저장
            print(visited)
            step = min(step, depth)
            return 
        }
        
        // 2. 매 원소를 돌며 다음에 올 수를 찾음
        for i in 0..<words.count {
            // 조건 (방문하지 않았고, 1개 문자만 차이나야 함)
            if !visited[i] && diff(start,words[i]) == 1 {
                // 방문 체크 
                visited[i] = true
                // 다음 원소 이동, depth + 1
                DFS(words[i],depth + 1)
                // 탐색 끝: 재귀 종료 후 가장 마지막 원소 방문기록 되돌리기             
                visited[i] = false                
            }     
        }        
    }
    DFS(begin,0)
    return step == Int.max ? 0 : step
}

func diff(_ o1: String, _ o2: String) -> Int {
    // 총 길이
    var count = o1.count
    for (n,m) in zip(o1,o2) {
        // 같으면 -1
        // count에 남는 수 만큼 문자가 다른 것이다. 
        if n == m {
            count -= 1
        }
    }    
    return count 
}

배열을 저장하는게 아니라 depth를 기준으로 판단하는 것이다. 

즉 현재 지정하고 있는 원소(start)가 target과 같을 경우 최소값을 비교하여 저장하여 리턴해주는 것이다. 

target과 같지 못한 경우, 즉 연결이 불가한 경우에 대해서는 삼항연산자로 커버하여 0으로 리턴시켜준다. 

---

이후 이동 가능한 선택지가 여러 개일 경우 재귀 이후 답이 없다면 visited[i] = false하여 다시 방문 가능하도록 해주는 것을 제대로 인지하지 못했다. 

 

DFS 응용에 대한 이해도가 떨어지는 것 같다... 이전에 풀었던 DFS 문제들을 다시 풀어보는 시간을 가져야겠다.

 

끄읕