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

https://programmers.co.kr/learn/courses/30/lessons/43163?language=swift 

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

BFS (너비 우선 탐색)

두 개의 단어 begin과 target이 주어지면 begin -> target으로 변환하는 최소 과정을 구하는 문제이다.

이때, begin을 target으로 변환하는 과정에서 한번에 한글자씩만 변환할 수 있고,

그렇게 변환할 단어가 words라는 배열에 속해있어야 한다.

 

요약하면 begin 단어를 words에 있는 단어들을 징검다리처럼 이용해서 최종적으로 target으로 변환하는 데에 필요한 최소한의 변환 횟수를 구하는 문제이다.

 

접근방법

최소 변환 횟수를 구하는 것이기 때문에 BFS를 사용했다. DFS를 사용해서 최소 변환 횟수를 갱신하면서 구할 수도 있겠지만 그렇게 되면 더 오래 걸리는 경우도 구해질 수 있기 때문에 비효율적이라고 생각했다.

 

(현재 갖고 있는 단어, 이 단어가 되기 까지의 변환 횟수) 형식의 tuple(String, Int)을 담을 큐를 사용했고,

words배열의 요소의 방문 여부를 저장하는 visit배열([Bool])을 사용했다.

visit 배열을 사용한 이유는 이전에 방문했던 단어를 또 방문하게 되는 경우는 이미 최소거리가 아니라는 뜻이므로 이 경우를 제외하고 bfs를 전개하고자 사용했다. 방문도 queue에 튜플을 append할때 체크해줬다. (그래야 bfs트리 상에서 같은 레벨에 있는 노드들도 제외하고 방문할 수 있음)

 

bfs 함수의 전개는 이렇다.

0. 큐에서 튜플하나를 pop해서 현재 갖고 있는 단어가 무엇인지 알 수 있다.

0-1. 현재 갖고 있는 단어가 target과 동일하면 cnt를 리턴 (cnt는 이 단어가 되기까지의 변환 횟수)

1. words 배열을 모두 확인하면서 다음으로 변환될 단어를 뽑아서 큐에 넣는다. (이때 새 단어와, 1 증가시킨 변환 횟수를 큐에 넣고, 다음으로 변환할 단어의 방문여부를 true로 갱신한다.)

1-1. words 배열에서 변환할 단어가 되는 것은 "1) 아직 방문하지 않았고, 2) 현재 갖고 있는 단어와 다른 글자가 1개뿐인 단어" 이다.

여기서 2)를 확인하는 함수가 isADifference이다. 두 단어를 받아서 둘의 글자 차이가 1개이면 true, 아니면 false를 반환한다.

 

+ words에 target 단어가 없는 경우 begin을 아무리 변환해도 target에 도달할 수 없으므로 함수 시작 부분에 이를 확인하여 처리한다.

 

소스코드

import Foundation

func solution(_ begin:String, _ target:String, _ words:[String]) -> Int {
    
    if !words.contains(target) {
        return 0
    }
    
    // bfs
    var visit:[Bool] = Array(repeating: false, count: words.count)
    var queue:[(begin:String, cnt:Int)] = []
    
    queue.append((begin, 0))
    
    while (!queue.isEmpty) {
        let here:(begin:String,cnt:Int) = queue.removeFirst()
        if(here.begin == target){
            return here.cnt
        }
        
        for (idx,word) in words.enumerated() {
            if !visit[idx] && isADifference(here.begin, word) {
                queue.append((word, here.cnt+1))
                visit[idx] = true
            }
        }
    }
    return 0
}

func isADifference(_ begin:String, _ next:String) -> Bool {
    let a:[Character] = Array(begin)
    let b:[Character] = Array(next)
    
    var cnt:Int = 0
    
    for i in 0..<a.count {
        if a[i] != b[i] {
            cnt += 1
            if cnt > 1 {
                return false
            }
        }
    }
    
    if cnt == 1 {
        return true
    }
    return false
}