1. 문제 설명

Eight puzzle

2. 문제 분석

파이썬으로 풀었을 때와 동일하게 풀었다. BFS를 통해 정답에서부터 가능한 모든 경우의 수 및 이동 횟수를 딕셔너리에 기록했고, 주어진 입력값이 없을 때에는 불가능함을 알 수 있었다. 스위프트에서는 큐가 자료구조 모듈로 제공되지 않기 때문에 일반 배열 사이즈 및 인덱스를 함께 사용한 테크닉을 통해 큐처럼 사용했다.

3. 나의 풀이

import Foundation

var answerNote:[String:Int] = [:]
let answer:[String] = ["1", "2", "3", "4", "5", "6", "7", "8", "9"]
let dx = [0, 0, 1, -1]
let dy = [1, -1, 0, 0]
func BFS()->Void{
    var queue = [([String], Int, Int)]()
    queue.append((answer, 0, 8))
    answerNote[answer.joined()] = 0
    var index = 0
    while queue.count > index{
        let curData = queue[index]
        let curState = curData.0
        let curCnt = curData.1
        let curPos = curData.2
        let curRow = curPos / 3
        let curCol = curPos % 3
        for i in 0..<4{
            let nextRow = curRow + dy[i]
            let nextCol = curCol + dx[i]
            if nextRow < 0 || nextCol < 0 || nextRow >= 3 || nextCol >= 3{
                continue
            }
            let nextPos = nextRow * 3 + nextCol
            var nextState = curState
            let tmp = curState[nextPos]
            nextState[nextPos] = "9"
            nextState[curPos] = tmp
            let nextStateString = nextState.joined()
            let nextCnt = answerNote[nextStateString, default: -1]
            if nextCnt == -1{
                answerNote[nextStateString] = curCnt + 1
                queue.append((nextState, curCnt+1, nextPos))
            }
        }
        index += 1
    }
}

let N = Int(readLine()!)!
BFS()
for _ in 0..<N{
    let _ = readLine()!
    var states = [String]()
    for _ in 0..<3{
        let row = readLine()!
        for letter in row{
            if String(letter) == "#"{
                states.append("9")
            } else {
                states.append(String(letter))
            }
        }
    }
    let curState = states.joined()
    let curCnt = answerNote[curState, default: -1]
    if curCnt == -1{
        print("impossible")
    } else{
        print(curCnt)
    }
}