[Swift 알고리즘] 백준 12919 A와 B 2

안녕하세요 코코종입니다.

오늘도 완전탐색!을 가지고 왔답니다.

첨에 좀 쉬워서 '왜 골드지?' 라고 생각했는데 역시나 틀렸어요 ㅎㅎ... 나눈 바보... 난이도 좀 볼걸

//
//  main.swift
//  BackJoon
//
//  Created by kokojong on 2023/04/16.
//

import Foundation

// 12919 A와 B 2 완전탐색

// 두 문자열 S와 T가 주어졌을 때, S를 T로 바꾸는 게임이다

// 문자열의 뒤에 A를 추가한다.
// 문자열의 뒤에 B를 추가하고 문자열을 뒤집는다.

var answer = 0

var s = readLine()!.map { return $0 == "A" ? 0 : 1 }
let t = readLine()!.map { return $0 == "A" ? 0 : 1 }
// A -> 0, B -> 1

func change1() { // 문자열 뒤에 A추가
    if t.count - s.count == 0 {
        if s == t {
            answer = 1
        }
        return
    }
    s.append(0)
    change1()
    change2()
    s.removeLast()
}

func change2() { // 문자열의 뒤에 B를 추가하고 문자열을 뒤집는다.
    if t.count - s.count == 0 {
        if s == t {
            answer = 1
        }
        return
    }
    
    s.append(1)
    s.reverse()
    change1()
    change2()
    s.reverse()
    s.removeLast()
}

change1()
change2()
print(answer)

네 완전 탐색으로 s가 t가 될수 있는지 판단하려고 했습니다. 하나하나 해서요! 근데 그랬더니 11퍼 ~ 12퍼에서 딱 시간초과가 뜨더라구요...

그래서 제가 chatGPT한테 물어봤더니 저렇게 말고 dfs로 해보라고 하더라구요? 그래서 stack에 넣고 뭐시기도 해봤는데도 시간초과가 뜨는거에요... 그래서 지피티랑 계속 떠들면서 했는데 결국 아무리해도 시간초과..... 하... 내 기존 코드가 문제인가 해서 다시 노려보고 👀 했는데도 이상한게 없더라구요... 참고로 저는 A B로 두기 싫어서 0과 1로 변경했습니다. 별 차이 없습니다 ㅎㅎ...

그래서 다른 분들의 블로그를 참고했더니 '역으로 오면서 체크'를 하더라구요... 하..... 그냥 완전탐색이라는거 보고 해버렸는데 어떻게 보면 함정?(나혼자 파고 나혼자 들어간) 이라고 생각 되네요. 역시 골드~~

//
//  main.swift
//  BackJoon
//
//  Created by kokojong on 2023/04/17.
//

import Foundation

// 12919 A와 B 2 완전탐색

// 두 문자열 S와 T가 주어졌을 때, S를 T로 바꾸는 게임이다

// 문자열의 뒤에 A를 추가한다. - case1
// 문자열의 뒤에 B를 추가하고 문자열을 뒤집는다. - case2

// 틀렸던 이유: s -> t가 아니라 t -> s로 해야한다.

let s = readLine()!.map { return $0 == "A" ? 0 : 1 }
let t = readLine()!.map { return $0 == "A" ? 0 : 1 }
// A -> 0, B -> 1
let n = t.count - s.count

// 반대로 하니까
// 끝이 A라면 -> case1(A를 빼줌)
// 맨 앞이 B라면 -> case2(뒤집고 맨뒤에 B를 빼줌)

func dfs(arr: [Int]) {
    if arr.count == s.count {
        if arr == s {
            print(1)
            exit(0)
        }
        return
    }
    
    let last = arr.last!
    if last == 0 {
        var tmp = arr
        tmp.removeLast()
        dfs(arr: tmp)
    }
    
    let first = arr.first!
    if first == 1 {
        var tmp = Array(arr.reversed())
        tmp.removeLast()
        dfs(arr: tmp)
    }
    
}

dfs(arr: t)
print(0)

T에서 해당하는 것만 dfs로 처리를 해주면 더 좁은 경우의 수만 처리할 수 있다! 라는 결론을 얻었습니다. 머리 쥐어싸매고 고민하느라 재밌었네요(사실 짜증남...)