→ Problems

[Algorithm] 백준 - 12919번 A와 B 2 (Swift)

Swift librarian 2024. 6. 12. 22:56

문제 소개

문제 풀이

BFS, DFS 두가지 풀이 방법이 있다. 시간은 둘다 22ms, 24ms 로 별 차이 없는 듯 하다.

BFS

import Foundation

let s = readLine()!
let t = readLine()!

func bfs() {
    var queue = [s]
    var idx = 0
    
    while queue.count > idx {
        let poped = queue[idx]
        idx += 1
        
        if poped == t {
            print(1)
            exit(0)
        }
        
        if poped.count > 50 { break }
        
        if t.contains(poped) || t.contains(String(poped.reversed())) {
            queue.append(poped + "A")
            queue.append(String((poped + "B").reversed()))
        }
    }
}

bfs()
print(0)

DFS

import Foundation

let s = readLine()!
let t = readLine()!

func dfs(_ current: String) {
    if current == t {
        print(1)
        exit(0)
    }
    
    if t.contains(current) || t.contains(String(current.reversed())) {
        dfs(current + "A")
        dfs(String((current + "B").reversed()))
    }
}

dfs(s)
print(0)