[알고리즘] Swift -프로그래머스 연습문제 #43163(단어 변환)

문제링크

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

프로그래머스

 

 

 

 

 

분석

begin target과 단어의 집합 words가 있을 때

 규칙을 이용하여 begin->target으로 변환하는 가장 짧은 변환 과정을 찾는다

 1. 한번에 한개의 알파벳만 바꿀 수 있다.

 2. words에 있는 단어로만 변환할 수 있다.

 

 begin: hit / target: cog

 words: [hot, dot, dog, lot, log, cog]

 hit hot dot dog cog 와 같이 4단계의 걸쳐 번환할 수이 있다.

 

풀이

import Foundation

var result = Int.max
var check: [Bool] = []

func solution(_ begin: String, _ target: String, _ words: [String]) -> Int {
    check = Array(repeating: false, count: words.count)
    dfs(begin, target, words, 0)
    return result == Int.max ? 0 : result
}

func dfs(_ begin: String, _ target: String, _ words: [String], _ count: Int) {
    if target == begin {
        result = result > count ? count : result
        return
    }
    for i in 0..<words.count {
        if !check[i] {
            var differences = 0

            for (char1, char2) in zip(begin, words[i]) {
                if char1 != char2 {
                    differences += 1
                }
                if differences > 1 {
                    break
                }
            }
            if differences == 1 {
                check[i] = words[i] == target ? false : true
                dfs(words[i], target, words, count + 1)
            }
        }
    }
}

 

결과

 

 

 

 

---

📂  정리

너무 어렵다

최솟값을 구하는 문제이기 때문에 초기값을 Int.max로 하고 작은값을 넣은 다음 마지막에 0이랑 reuslt를 구분하여 출력한다