[Swift][BFS] 백준 12906번 (새로운 하노이 탑)

요구능력 : Set, BFS

 

코드설명 : 

 

원판움직이는 경우를 BFS로 표현하는것은 어렵지 않다.

A에 원판이 있는경우 하나를 빼서 B에 넣는경우를 큐에 넣어주고 C에 넣는경우를 큐에 넣어주면된다.

B와 C도 마찬가지로 하면된다.

 

이 문제에서 가장 중요한점은 방문처리를 어떻게 하느냐이다.

나는 처음에 방문처리를 안했다가 무한루프에 빠지고 말았다.

 

이런문제를 나처럼 처음 접하는 사람들은 당황하게 될 것이다.

방문처리를 해야되는데,, 문자열이네?

여태 좌표만 방문처리해봐서 문자열은 할줄 모르겠다 싶었다.

 

Set을 활용하면 되더라.

다른 언어들은 Set에 큐에 사용한 형식그대로 사용하는데, Swift는 따로 custom을 해줘야한단다.

그냥 String으로 처리해줘야겠다.

각 모든 배열을 joined()로 string문자열로 만들어주고 ,로 구분해서 set에 추가해줬다.

 

이런식으로 방문처리를 하면 아니 해야되는 이유는 문자열을 따로 배열로 방문처리할 방법은 뭐 있을 수도 있지만, 있다하더라도 시간내에 코드가 통과할 수 없을것이다.

 

Set은 Hash값으로 값을 찾기 때문에 contains()를 사용해도 시간복잡도가 O(1)이 나온다.

 

앞으로 문자열 방문처리를 해야된다고 느낀다면 Set을 잘 활용하면 되겠다.

 

후기 : 뭔가 노가다를 곁들인 문제같다.

 

import Foundation
//막대 A에는 원판 A만, 막대 B는 원판 B만, 막대 C는 원판 C만 놓여져 있어야 한다.
let aArr = readLine()!.split(separator: " ").map{String($0)}
let bArr = readLine()!.split(separator: " ").map{String($0)}
let cArr = readLine()!.split(separator: " ").map{String($0)}

let aCount = Int(aArr[0])!//원판의 개수
let bCount = Int(bArr[0])!
let cCount = Int(cArr[0])!

var aStatus = [String]()
var bStatus = [String]()
var cStatus = [String]()

if aCount > 0 {
    aStatus = aArr[1].map{String($0)}
}
if bCount > 0 {
    bStatus = bArr[1].map{String($0)}
}
if cCount > 0{
    cStatus = cArr[1].map{String($0)}
}

func bfs(_ aStatus: [String], _ bStatus: [String], _ cStatus: [String]){
    var queue = [(([String], [String], [String]), Int) ]()
    queue.append(((aStatus, bStatus, cStatus), 0))
    var visited = Set<String>()
    visited.insert("\(aStatus.joined(separator: "")), \(bStatus.joined(separator: "")), \(cStatus.joined(separator: ""))")
    var idx = 0
    while queue.count > idx{
        let pop = queue[idx]
        idx += 1
        let a = pop.0.0
        let b = pop.0.1
        let c = pop.0.2
        if !a.contains("B") && !a.contains("C") && !b.contains("A") && !b.contains("C") && !c.contains("A") && !c.contains("B") {
            print(pop.1)
            break
        }

        if a.count > 0 {
            var calculatedA = a
            var calculatedB = b
            var calculatedC = c
            let popedA = calculatedA.removeLast()
            calculatedB.append(popedA)
            calculatedC.append(popedA)
            
            let calAtoString = calculatedA.joined()
            let calBtoString = calculatedB.joined()
            let calCtoString = calculatedC.joined()

            let atoString = a.joined()
            let btoString = b.joined()
            let ctoString = c.joined()
            
            
            if !visited.contains("\(calAtoString), \(calBtoString), \(ctoString)"){
                queue.append(((calculatedA, calculatedB, c), pop.1 + 1))//A에서 뺴고 B에서 넣고
                visited.insert("\(calAtoString), \(calBtoString), \(ctoString)")
            }
            if !visited.contains("\(calAtoString), \(btoString), \(calCtoString)"){
                queue.append(((calculatedA, b, calculatedC), pop.1 + 1)) //A에서 빼고 B에서 넣고
                visited.insert("\(calAtoString), \(btoString), \(calCtoString)")
            }
            

        }
        if b.count > 0 {
            var calculatedA = a
            var calculatedB = b
            var calculatedC = c
            let popedB = calculatedB.removeLast()
            calculatedA.append(popedB)
            calculatedC.append(popedB)
            
            let calAtoString = calculatedA.joined()
            let calBtoString = calculatedB.joined()
            let calCtoString = calculatedC.joined()

            let atoString = a.joined()
            let btoString = b.joined()
            let ctoString = c.joined()
            
            if !visited.contains("\(calAtoString), \(calBtoString), \(ctoString)"){
                queue.append(((calculatedA, calculatedB, c), pop.1 + 1))//B에서 뺴고 A에서 넣고
                visited.insert("\(calAtoString), \(calBtoString), \(ctoString)")
            }
            if !visited.contains("\(atoString), \(calBtoString), \(calCtoString)"){
                queue.append(((a, calculatedB, calculatedC), pop.1 + 1)) //B에서 빼고 C에서 넣고
                visited.insert("\(atoString), \(calBtoString), \(calCtoString)")
            }
        }

        if c.count > 0 {
            var calculatedA = a
            var calculatedB = b
            var calculatedC = c
            let popedC = calculatedC.removeLast()
            calculatedA.append(popedC)
            calculatedB.append(popedC)
            
            let calAtoString = calculatedA.joined()
            let calBtoString = calculatedB.joined()
            let calCtoString = calculatedC.joined()

            let atoString = a.joined()
            let btoString = b.joined()
            let ctoString = c.joined()
            
            if !visited.contains("\(calAtoString), \(btoString), \(calCtoString)"){
                queue.append(((calculatedA, b, calculatedC), pop.1 + 1))//C에서 뺴고 A에서 넣고
                visited.insert("\(calAtoString), \(btoString), \(calCtoString)")
            }
            if !visited.contains("\(atoString), \(calBtoString), \(calCtoString)"){
                queue.append(((a, calculatedB, calculatedC), pop.1 + 1)) //C에서 빼고 B에서 넣고
                visited.insert("\(atoString), \(calBtoString), \(calCtoString)")
            }

        }
    }

}
bfs(aStatus, bStatus, cStatus)