[프로그래머스] (Swift) 단어변환 (LV.3) (DFS)

⚫️ 문제

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

프로그래머스

 

⚫️ 나의 생각의 흐름

일단 몇단계의 흐름을 거쳐야하는지 , 그리고 이 흐름이 최소가 되는 해를 구해야한다. 그렇기 때문에 일단 가장 먼저 BFS를 떠올렸다. 그럼 BFS를 구현하기 전에 이것저것 생각을 해보자.

🔖 시간복잡도

조건을 살펴보고 시간복잡도를 생각해봤다. BFS를 구현하면 총 N번의 노드에 방문하고, queue가 빌때까지 while문이 반복되므로 O(n^2)의 시간복잡도를 갖는다. 그리고 앞에서 항상 말했듯, BFS는 queue의 성능이 굉장히 중요한데, 가장 좋은 건 O(1)짜리 큐를 갖는 것이지만, 범위가 해볼만하다면, 과감하게 removeFirst를 써도 시간초과가 나지 않는다. 지금 이 경우는 queue 내부에 가장 많은 데이터가 들어가도 2500개이기 때문에 뭐.. 나쁘지 않다고 생각했다. (아직은 이정도로 추측하는 정도이지만, 조만간 더 자세히 시간복잡도에 대해서 공부하고 글을 포스팅해보겠다! 👊🏻)

🔖 그럼 , BFS로 구현해보기로 하고 수도코드로 작성해보자.

일단 BFS는 내가 원하는 노드까지 도달하게 되면, 바로 while문을 탈출하고 그 노드까지 간 cost 를 출력한다. 이 방식을 이용하고자 했다. 그럼 여기서 뭐가 노드가 될까?

문제의 조건이, hit begin으로 주어진다면 '한 알파벳'이 다른 것이 다음으로 올 수 있다. 얘재 1번을 예시로 보면, hit 다음으로는 hot이 올 수 있겠지? 그러 hit과 인접한 노드를 hot이라고 생각하고 hot을 다음 큐에 넣어준다. 이런식으로 DFS를 구현하면 되지 않을까?

문제의 조건에서 '한 글자만 바꿀 수 있다'라고 한 것은, 결국 한글자 빼고 알파벳의 위치는 모두 같아야한다. hit 과 hot처럼! 그래서 이렇게 한글자만 다른 것을 구별해주는 함수를 따로 만들었다. (가독성을 위해 노력해봤다 ^___^ 👊🏻)

이 문제를 풀면서 zip을 처음 써봤는데, hit과 hot을 zip을 이용하게 된다면, h-h, i-o, t-t 이렇게 짝지어서 loop를 돌 수 있게 만들어준다. 보통 for문에서 많이 사용한다고 한다! 어쨌든 이 zip을 이용하고, filter로 비교해주었다.

func canChange(word: String, changeWord: String) -> Bool {
    if zip(word, changeWord).filter({ $0 != $1 }).count == 1 {
        return true
    }
    return false
}

 

⚫️ 정답코드

import Foundation

func solution(_ begin:String, _ target:String, _ words:[String]) -> Int {
    if !words.contains(target) {
        return 0
    }

    // bfs
    var queue = [(String, Int)]()
    queue.append((begin, 0))

    while !queue.isEmpty {
        let temp = queue.removeFirst()
        let word = temp.0
        let depth = temp.1

        for w in words {
            if canChange(word: word, changeWord: w) {
                if w == target {
                    return depth + 1
                } else {
                    queue.append((w, depth + 1))
                }
            }
        }
    }

    return 0
}

func canChange(word: String, changeWord: String) -> Bool {
    if zip(word, changeWord).filter({ $0 != $1 }).count == 1 {
        return true
    }
    return false
}