출처: 프로그래머스 코딩 테스트 연습

문제 설명

두 개의 단어 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단계를 거쳐 변환할 수 있습니다.

두 개의 단어 begin, target과 단어의 집합 words가 매개변수로 주어질 때, 최소 몇 단계의 과정을 거쳐 begin을 target으로 변환할 수 있는지 return 하도록 solution 함수를 작성해주세요.

제한 사항

• 각 단어는 알파벳 소문자로만 이루어져 있습니다.

• 각 단어의 길이는 3 이상 10 이하이며 모든 단어의 길이는 같습니다.

• words에는 3개 이상 50개 이하의 단어가 있으며 중복되는 단어는 없습니다.

• begin과 target은 같지 않습니다.

• 변환할 수 없는 경우에는 0를 return 합니다.

입출력 예

begin	target	words
"hit"	"cog"	["hot", "dot", "dog", "lot", "log", "cog"]
"hit"	"cog"	["hot", "dot", "dog", "lot", "log"]

입출력 예 설명

예제 #1
문제에 나온 예와 같습니다.

예제 #2
target인 "cog"는 words 안에 없기 때문에 변환할 수 없습니다.

내가 제출한 코드

import Foundation

class Words {
    let name: String
    let dis: Int
    
    init(_ name: String, _ dis: Int) {
        self.name = name
        self.dis = dis
    }
}

struct Queue<T> {
    private var items = [T]()
    
    public mutating func enqueue(_ item: T) {
        items.append(item)
    }
    public mutating func dequeue() ->T? {
        return (items.isEmpty) ? nil : items.removeFirst()
    }
    public func peek() ->T? {
        return items.first
    }
    public func isEmpty() -> Bool {
        return (items.isEmpty) ? true : false
    }
}

func solution(_ begin:String, _ target:String, _ words:[String]) -> Int {
    var wordQueue = Queue<Words>()
    var answer: Int = 0 // 변환 횟수
    var visited: [Bool] = Array(repeating: false, count: words.count) // 방문배열
    
    wordQueue.enqueue(Words(begin,0)) // init
    
    while !wordQueue.isEmpty() { // queue가 빌때까지
        guard let curWord = wordQueue.dequeue() else {
            print("error")
            return -1
        }
        if curWord.name == target { // target을 찾은 경우
            answer = curWord.dis
            break
        }
        
        for (index,word) in words.enumerated() {
            if !visited[index] && checkTrans(curWord.name,word){ // 다음 단어로 변환할 수 있는 경우
                wordQueue.enqueue(Words(word,curWord.dis + 1))
                visited[index] = true
            }
        }
    }
    
    return answer
}

// curWord가 nextWord로 변환할 수 있는 지 확인
func checkTrans(_ curWord: String, _ nextWord: String) -> Bool {
    let word1 = curWord.map{String($0)}
    let word2 = nextWord.map{String($0)}
    let N: Int = curWord.count
    var answer = 0;
    
    for i in 0..<N {
        if word1[i] == word2[i] {
            answer += 1
        }
    }
    return (answer == word1.count - 1) ? true : false
    
}

코드 설명

이번 문제의 카테고리는 DFS(깊이 우선 탐색)/BFS(너비 우선 탐색)이다. 우리가 구하고자 하는 것은 begin에서 target까지 가장 짧은 변환 과정의 횟수이다. 이럴 경우 BFS 알고리즘을 선택하면 된다. BFS 알고리즘은 그래프의 탐색을 현재 노드를 중심으로 동심원 형태로 탐색하기 때문에 최단 관련 문제에 더 적합하다.

풀이는 코드를 보면서 자세히 설명한다.

Words 클래스의 구현부이다.

class Words {
    let name: String
    let dis: Int
    
    init(_ name: String, _ dis: Int) {
        self.name = name
        self.dis = dis
    }
}

name 프로퍼티는 word의 이름 즉 단어가 할당된다. dis 프로퍼티에는 입력으로 들어온 begin에서 현재의 단어까지 몇 번의 변환을 거쳤는지 나타내는 변환 횟수가 저장된다.

큐를 구현하는 부분은 설명을 생략한다. 큐를 이용하여 BFS를 사용한다는 사실만 알아두자.

아래 코드에서 중복 탐색을 방지하는 visited 배열을 나타내는 프로퍼티를 확인할 수 있다.

var wordQueue = Queue<Words>()
var answer: Int = 0 // 변환 횟수
var visited: [Bool] = Array(repeating: false, count: words.count) // 방문배열
    
wordQueue.enqueue(Words(begin,0)) // init

우선 BFS탐색을 하는 경우, 중복된 단어를 탐색하는 것을 방지하기 위해 visited을 선언하였다. 이 방법 대신 여러가지 방법이 존재한다. 예를 들어 현재 코드는 큐에서 탐색한 단어를 반출한 후, 해당 단어와 변환할 수 있는 단어를 찾기 위해 입력으로 들어온 n개의 단어 모두 탐색하지만, 이미 큐에 들어온 단어를 배열에서 제거하면 반출마다 n개를 탐색하는 것이 아닌 n - 큐에 반입된 횟수만큼 탐색한다.

다음으로 시작 단어에서 words 배열에 담긴 단어들로 변환을 수행하는 코드이다.

while !wordQueue.isEmpty() { // queue가 빌때까지
        guard let curWord = wordQueue.dequeue() else {
            print("error")
            return -1
        }
        if curWord.name == target { // target을 찾은 경우
            answer = curWord.dis
            break
        }
        
        for (index,word) in words.enumerated() {
            if !visited[index] && checkTrans(curWord.name,word){ // 다음 단어로 변환할 수 있는 경우
                wordQueue.enqueue(Words(word,curWord.dis + 1))
                visited[index] = true
            }
        }
    }

반복문은 큐가 빌 때까지 실행된다. 즉 시작 단어에서 변환할 수 있는 모든 단어를 queue에 반입하였다가 다시 반출한 경우 반복문이 종료된다.

우선 큐에서 반출한 프로퍼티를 curWord라 한다. 여기서 curWord는 단어 자체("hot"가 아닌 단어와 변환 과정을 포함하는 Words 클래스 타입이라는 것을 기억하자. 큐에서 꺼낸 인스턴스의 단어의 이름이 target과 같다면 즉시 종료한다. 이유는 BFS 알고리즘을 사용했기 때문에, 해당 인스턴스의 dis는 최소의 변환 횟수를 가지고 있다. 그러므로 최종적으로 이를 반환하면 된다.

다음 단어로 변환 여부를 확인하기 위해 for문 에서 2가지 조건을 확인한다. 중복 탐색 여부와 두 단어가 한 개의 알파벳만 차이 나는지 확인하는 것이다. 만약 2가지 모두 만족한다면 해당 단어로 변환할 수 있기 때문에 이를 큐에 반입하게 된다. 단, 변환 횟수를 현재 변환 횟수 + 1로 할당해야 한다. (wordQueue.enqueue(Words(word,curWord.dis + 1)))

마지막으로 2개의 단어가 1개의 알파벳만 다르고 나머지 알파벳만 같은지 확인하는 함수 checkTrans의 코드이다.

func checkTrans(_ curWord: String, _ nextWord: String) -> Bool {
    let word1 = curWord.map{String($0)}
    let word2 = nextWord.map{String($0)}
    let N: Int = curWord.count
    var answer = 0;
    
    for i in 0..<N {
        if word1[i] == word2[i] {
            answer += 1
        }
    }
    return (answer == word1.count - 1) ? true : false    
}

방법은 단순하다. 2개의 단어의 길이는 같다. 그러므로 단어의 길이만큼 반복문을 통해 두 단어의 각 문자를 비교한다. 만약 서로 변환이 가능하다면 answer 프로퍼티의 값은 단어의 길이 - 1가 된다. 이를 통해 두 단어가 변환 가능한지 확인한다.