프로그래머스 단어 변환 문제 (Swift 풀이)

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

프로그래머스

 

풀이 코드

import Foundation
 
func solution(_ begin:String, _ target:String, _ words:[String]) -> Int {
    var queue = Queue<(String,[String])>()
    var result = 0
    words.forEach {
        if isCousin($0, begin) {
            if $0 == target {
                result = 1
            }
            var array = words
            var index = array.firstIndex(of: $0)!
            array.remove(at: index)
            
            queue.enqueue(($0,array))
        }
    }
    
    repeat {
        let temp = queue.dequeue()!
        
        temp.1.forEach {
            if isCousin($0, temp.0) {
                if $0 == target {
                    result = (words.count - temp.1.count + 1)
                } else {
                    var array = temp.1
                    var index = array.firstIndex(of: $0)!
                    array.remove(at: index)
                    
                    queue.enqueue(($0,array))
                }
            }
        }
        
    } while !queue.isEmpty && result == 0
    
    return result
}
 
func isCousin(_ a: String, _ b: String) -> Bool {
    var k = 0
    var stringA = a.map { $0 }
    var stringB = b.map { $0 }
    
    stringA.enumerated().forEach {
        if $1 != stringB[$0] {
            k += 1
        }
    }
    
    if k == 1 {
        return true
    } else {
        return false
    }
}
 
struct Queue<T> {
    private var queue: [T] = []
    
    public var count: Int {
        return queue.count
    }
    
    public var isEmpty: Bool {
        return queue.isEmpty
    }
    
    public mutating func enqueue(_ element: T) {
        queue.append(element)
    }
    
    public mutating func dequeue() -> T? {
        return isEmpty ? nil : queue.removeFirst()
    }
}
 

풀이 과정

최단거리 문제가 떠올라 BFS풀이를 떠올렸다.

<인접한 노드(변환될 수 있는 문자)인지를 판단하는 isCousin 함수를 통해 변환 가능 여부를 체크하고 가능하면 해당 노드로 방문한다>가 핵심 아이디어였다.

이때 방문하기로 한 노드가 만약 target과 같다면 정답이 된다.

repeat의 매 반복마다 같은 레벨의 모든 요소들을 탐색하도록 구현하였다.

덕분에 가장 먼저 target에 도달한 경우의 level이 바로 문제에서 요구하는 최소 단계값이 된다.

 

배운 점

BFS 알고리즘에선 탐색에 들어가기 전에 가장 처음 탐색을 진행할 요소들을 큐에 집어넣는 작업(7~18번 줄) 을 진행하곤 한다.

이 문제에서도 마찬가지로 진행하였는데 문제의 testcase에 첫 탐색을 위한 요소들 중 바로 정답이 되는 요소가 섞여있는 testcase가 

있어 디버깅을 하는데 오래걸렸다.  ( TestCase1. "hit", "hot", ["hit", "hot", "lot"] = 1 )

해당 작업을 진행할 때도 정답이 되는 경우를 걸러내는 작업이 필요하다. (9~11번 줄)