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

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

[프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

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

2023.07.05 기준 Level 3

알고리즘 공부용으로 풀고 기록하는 글입니다!
참고만 해주시고 더 좋은 풀이법이 있다면 알려주세요!

아이디어

begin으로 주어진 문자열을 target 문자열로 바꾸기 위해 몇번의 단계(Step)이 필요한지 구하는 문제입니다.

각 단어끼리 비교해서 하나의 알파벳만 다를 때 한 Step 을 진행할 수 있기 때문에 우선 단어를 비교해서 한가지 알파벳만 다른지 파악하는 함수를 만들어야 합니다.

그리고 결국 가능한 경우의 모든 단어들을 탐색해서 가장 최적의 경로를 찾아야 하기 때문에 DFS 혹은 BFS로 풀 수 있습니다!

저는 BFS로 풀어보았습니다.

1. words 배열에서 주어진 단어들을 전부 비교해서 하나의 알파벳만 다른 단어들을 큐에 넣는다.

2. while 문을 돌며 queue에서 단어를 빼고 1번의 작업을 반복

3. target 문자열까지 도달하면 return

풀이

fileprivate func solution(_ begin:String, _ target:String, _ words:[String]) -> Int {
    var result = Int.max

    func bfs() {
        var queue = [String]()
        var step = [String: Int]()  // 각 단어까지 접근하기 위한 단계를 저장

        queue.append(begin)
        step[begin] = 0

        while !queue.isEmpty {
            let first = queue.removeFirst()

            if first == target {
                result = min(result, step[first]!)
                return
            }

            for word in words {
                if step[word] != nil { continue }
                if isOneAlphabetDifference(word1: first, word2: word) {
                    step[word] = step[first, default: 0] + 1

                    queue.append(word)
                }
            }
        }
    }

    bfs()

    return result == Int.max ? 0 : result
}

// 두 단어가 알파벳 하나 차이인지 체크
fileprivate func isOneAlphabetDifference(word1: String, word2: String) -> Bool {
    var diffCnt = 0
    for i in word1.indices {
        if word1[i] != word2[i] { diffCnt += 1 }
        if diffCnt > 1 { return false }
    }

    return diffCnt == 1 ? true : false
}

두 단어가 알파벳 하나의 차이인지 체크하는 함수인 isOneAlphabetDifference 함수를 생성했습니다.

그리고 각 단어까지 도달한 단계를 기록하기 위해 step 이라는 이름으로 딕셔너리를 생성했습니다.

 

key 값으로는 각 단어가 들어가고 value에는 해당 단어까지 도달하기 위한 단계가 들어갑니다.

stemp[word] != nil 인경우는 이미 방문한 단어이기 때문에 다시 탐색하지 않도록 했습니다.

 

나머지는 일반적인 BFS 풀이법을 사용했습니다.

 

마무리

일반적인 탐색 문제였습니다.

저는 BFS를 사용했으나 DFS로 푼 답안들도 많이 있습니다..!

각 단어 별 도달 단계를 저장하기 위해 딕셔너리를 사용해 보았습니다!