[Swift] [91일차] 단어변환_Programmers

단어변환으로 만든 DALLE이미지

단어변환

---

문제 설명

1. begin,target , words배열 이렇게 주어진다.
2. begin에서 시작해서 target으로 도달하기 위한 카운트를 구하라(최소)
   3.words안에서 골라서 바꿔가야되고, 그 과정에서 바꾸기위해서는 두 단어가 문자 하나만 달라야 바꿀 수 있다.

---

문제 풀이

1. 이렇게 뭘 변환해서 도달하는거는 결국 BFS/DFS쪽이라 생각을해서 그 부분으로 풀이방향을 잡았다.
2. 핵심은 이걸 어떻게 <두 단어끼리 문자 1개만 다른 것을 빠르게 판단할 수 있는 함수>를 만들어낼 것인가 였던 것 같다.
3. 나머지는 그냥 일반적인 DFS/BFS포맷으로 접근하면 될 것이었는데, 뭔가 뒤에서부터 시작을 해야 확실하게 경로가 보일거라고 근거없이 생각한 탓에 좀 더 해매는 시간이 걸렸다.

import Foundation

func solution(_ begin: String, _ target: String, _ words: [String]) -> Int {
    guard words.contains(target) else { // 타겟없으면 나 안해 !
        return 0
    }

    var answerArr = [Int]()
    var visited = Array(repeating: false, count: words.count)
    visited[words.firstIndex(of: target)!] = true // 첫 항시작이니까
    func dfs(cnt: Int, current: String, visited: inout [Bool]) {
       if(current == begin){
       	answerArr.append(cnt)
       }
        for (idx, item) in words.enumerated() {
            if !visited[idx] && canChangeArr(compare1: current, compare2: item) {
                visited[idx] = true
                if item == begin {
                    print("HI")
                }
                dfs(cnt: cnt + 1, current: item, visited: &visited)
                visited[idx] = false
            }
        }
    }

    func canChangeArr(compare1: String, compare2: String) -> Bool {
        return zip(compare1, compare2).filter { $0 != $1 }.count == 1
    }
    dfs(cnt: 0, current: target, visited: &visited)

    return min(answerArr)
}

풀다가 카운팅 다른데에다하면 찍히는거는 같은데 어떻게 한명도 도달을 하지않을까??해서 계속 다른부분을 수정해주다보니,, 내가 이걸 뒤집은 상태로하니까 당연히 words배열안에는 begin이 없었던 것 !

그래서 아래처럼 유니콘을 찾던 로직을 지우고 ,

if(current == begin){
	answerArr.append(cnt)
    }

목표랑 한글자만 다르면 바로 끝내주는 방향으로 로직을 수정했다. (끝에서 시작하니까 + 1 도 필수)

if canChangeArr(compare1: current, compare2: begin) {
            answerArr.append(cnt + 1)
        }

마지막으로 그렇게 뽑아낸 dfs()의 결과물들을 모은 배열 [Int]에서 min()!으로 최솟값 빼주면 끝이다 !

최종 제출 코드

import Foundation

func solution(_ begin: String, _ target: String, _ words: [String]) -> Int {
    guard words.contains(target) else { // 타겟없으면 나 안해 !
        return 0
    }

    var answerArr = [Int]()
    var visited = Array(repeating: false, count: words.count)
    visited[words.firstIndex(of: target)!] = true // 첫 항시작이니까
    func dfs(cnt: Int, current: String, visited: inout [Bool]) {
        if canChangeArr(compare1: current, compare2: begin) {
            answerArr.append(cnt + 1)
        }
        for (idx, item) in words.enumerated() {
            if !visited[idx] && canChangeArr(compare1: current, compare2: item) {
                visited[idx] = true
                
                dfs(cnt: cnt + 1, current: item, visited: &visited)

            }
        }
    }

    func canChangeArr(compare1: String, compare2: String) -> Bool {
        return zip(compare1, compare2).filter { $0 != $1 }.count == 1
    }
    dfs(cnt: 0, current: target, visited: &visited)

    return answerArr.min()!
}

채점 결과

정확성: 100.0
합계: 100.0 / 100.0

---

BFS로 풀어보기

이번에는 타인의코드보다는 BFS에 더 적합한 문제라고 느껴서 BFS로도 풀이를 진행했다.
canChangeArr를 통해서 점검한다던지 하는 로직은 동일하다.

import Foundation

func solution(_ begin: String, _ target: String, _ words: [String]) -> Int {
    guard words.contains(target) else { // 타겟없으면 나 안해 !
        return 0
    }

    var visited = Array(repeating: false, count: words.count)

    var queue = [(cnt: 0, current: begin)]

    while !queue.isEmpty {
        let now = queue.removeFirst()
        let now_cnt = now.cnt
        let now_str = now.current
        if now_str == target {
            return now_cnt
        }

        for (idx, item) in words.enumerated() {
            if canChangeArr(now_str, item), !visited[idx] {
                visited[idx] = true
                queue.append((cnt: now_cnt + 1, current: item))
            }
        }
    }
    func canChangeArr(_ compare1: String, _ compare2: String) -> Bool { // 변경 가능한 친구들을 모아놓은 ARR
        return zip(compare1, compare2).filter { $0 != $1 }.count == 1 ? true : false
    }

    return 0
}

뭐에 홀린듯이 뒤에서부터 풀었는데, 그래야 더 쉽게 풀린다고 생각을 했었다. 왜 그랬는지는 모르겠지만.. 사실 BFS풀이도 첨엔 뒤에서부터 풀다가, 이거 그럴 필요가 없는 것 같아서 수정하니까 훨씬 더 간결하게 답을 찾을 수 있었다.