[Programmers] 단어 변환 (Swift)

문제 :

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

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

 

1. 문제 이해하기

• 두 단어 begin, target, 단어의 집합 words가 주어집니다.
• begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다.
• 해당 조건으로만 단어를 변환할 수 있습니다.
  

  1. 한 번에 한 개의 알파벳만 바꿀 수 있습니다.
  2. words에 있는 단어로만 변환할 수 있습니다.

 

2. 문제 풀이 생각하기

1. bfs, dfs 중 dfs로 문제 풀이를 생각했습니다. 방문 체크를 하지 않는 단어를 기준으로 모든 단어를 dfs로 돌고 이미 방문한 노드는 방문처리를 하는 방식으로 해야겠다고 생각했습니다.
2. begin == target이 되면 ans에 최솟값 갱신
3. 그 이외에는 for문으로 begin을 기준으로 모든 단어를 방문
4. begin과 다음 단어를 비교해서 알파벳이 몇 개 차이 나는지 개수 세기
5. 틀린 알파벳 차이가 1개 일 때만 다음 단어를 방문 체크하고 해당 단어를 기준으로 dfs 시작, 시작하면서 시행 횟수(cnt) + 1
6. 2 ~ 5 반복
7. ans 리턴

 

테스트 케이스로 예시를 들어보겠습니다. 

hot -> dot -> got -> cog 가 답입니다.

하지만 밑에 hit -> hot -> iot -> hot -> dot -> dog -> cog 도 답이 될 수 있습니다.

이렇게 방문했던 곳을 다시 방문하면 최단 거리가 될 수 없고, 무한루프에 빠질 수 있기 때문에 방문 처리를 해주어야 합니다.

 

3. 차근차근 구현하기

import Foundation

var ans = Int.max
var visited = [Bool]() // 방문 체크

func solution(_ begin:String, _ target:String, _ words:[String]) -> Int {
    visited = Array(repeating: false, count: words.count)
    dfs(begin, target, words, 0)
    
    return ans == Int.max ? 0 : ans // 변환할 수 있으면 ans, 변환할 수 없으면 0
}
    
func dfs(_ begin: String, _ target: String, _ words: [String], _ cnt: Int) {
    if begin == target {
        // ans를 작은 값으로 갱신
        ans = ans > cnt ? cnt : ans
        return
    }
    else {
        // begin을 기준으로 모든 단어를 방문
        for i in 0..<words.count {
            if visited[i] {
                continue
            }

            let beginArr = Array(begin).map{String($0)}
            let wordCache = Array(words[i]).map{String($0)}
            var numOfDifferent = 0

            // begin과 다음 단어 간 틀린 알파벳 개수 비교
            for j in 0..<beginArr.count {
                if beginArr[j] != wordCache[j] {
                    numOfDifferent += 1
                }
            }
            
            // 틀린 알파벳 개수가 하나일 때만 다음 단어를 방문 체크하고 다음 단어를 기준으로 dfs 시작
            if numOfDifferent == 1 {
                // begin이 target이 되는 방법이 여러 개가 될 수 있기 때문에 target 인덱스는 방문 체크를 하지 않고 그 이외에는 방문 체크
                visited[i] = words[i] == target ? false : true
                dfs(words[i], target, words, cnt + 1)
            }
        }
    }
}

 

4. 피드백

• dfs에 재미를 느끼고 있습니다.