백준 17825 주사위 윷놀이

출처: www.acmicpc.net/problem/17825

분류: 완전탐색

---

접근방식

꽤나 시간이 오래 걸렸던 문제네요..

저는 5개의 루트로 나눠서 생각을 해봤는데요, 

이동하고 나서 해당 칸이 다른 루트로 가야 한다면 루트를 바꿔주는 방식으로 풀었습니다.

이런 식으로 루트를 생각하면 다음과 같이 초기화 해줄 수 있습니다.

var root = [[Int]](repeating: [Int](), count: 5)
root[0] = (0...19).map { $0 * 2 }
root[1] = [0, 13, 16, 19]
root[2] = [0, 22, 24]
root[3] = [0, 28, 27, 26]
root[4] = [25, 30, 35, 40, 0]

1, 2, 3 같은 경우 특정 칸에서 멈출 때만 이동하고, 루트0에서 점수를 얻고 해당 루트로 갈아타주기 때문에
처음에 0을 넣어서 해당 루트의 0번째 칸으로 바꿔주도록 했습니다.

4번 루트 같은 경우는 1, 2, 3루트에서 더 커지면 그대로 루트4로 넘어가서 계속 이동해야 하기 때문에 처음 0이 없습니다.

처음에 실수했던 부분은 중복을 체크해줘야 하기 때문에 마지막 40도 하나의 루트로 통일시켜줘야 합니다. 처음엔 루트0에서 40으로, 루트4에서 40으로를 각각 두고 생각했었는데, 이 부분에서 실수가 있었습니다 😬

 

그리고 각 말이 어떤 루트의 어떤 포지션에 있는지 확인하기 위해서 typealias 로 타입을 하나 지정해줬습니다.

typealias Horse = (root: Int, position: Int)

 

이제 특정 말이 몇 칸 점프해야 하는지 알면 다음 위치와 점수를 알 수 있겠죠? 이를 수행하는 함수를 하나 만들었습니다.
말을 바로 이동시키지 않고 이렇게 리턴하도록 한 이유는 이동하려는 위치에 말이 있으면 안 되기 때문에 이 부분은 밖에서 처리해주도록 이 부분까지만 함수로 분리시켰습니다.

func move(_ horse: Horse, jump: Int) -> (Horse, Int) {
    switch horse.root {
        case 0:
            let nextPosition = horse.position + jump
            
            if nextPosition > 20 {
                return ((4, 4), 0)
            } else if nextPosition == 20 {
                return ((4, 3), 40)
            } else if root[0][nextPosition] == 10 {
                return ((1, 0), root[0][nextPosition])
            } else if root[0][nextPosition] == 20 {
                return ((2, 0), root[0][nextPosition])
            } else if root[0][nextPosition] == 30 {
                return ((3, 0), root[0][nextPosition])
            } else {
                return ((0, nextPosition), root[0][nextPosition])
            }
        case 1:
            if horse.position + jump > 3 {
                return ((4, horse.position + jump - 4), root[4][horse.position + jump - 4])
            } else {
                return ((1, horse.position + jump), root[1][horse.position + jump])
            }
        case 2:
            if horse.position + jump > 2 {
                return ((4, horse.position + jump - 3), root[4][horse.position + jump - 3])
            } else {
                return ((2, horse.position + jump), root[2][horse.position + jump])
            }
        case 3:
            if horse.position + jump > 3 {
                return ((4, horse.position + jump - 4), root[4][horse.position + jump - 4])
            } else {
                return ((3, horse.position + jump), root[3][horse.position + jump])
            }
        case 4:
            let nextPosition = min(4, horse.position + jump)
            return ((4, nextPosition), root[4][nextPosition])
        default:
            fatalError("invalid root")
    }
}

 

이제 진짜 게임을 플레이 해주면 됩니다. 백트래킹 방식으로 풀어줬습니다!

이동하려는 칸이 마지막이 아닌데 다른 말이 있다면 움직일 수 없겠죠?

func play(_ turn: Int, _ point: Int) {
    guard turn < 10 else {
        if maxPoint < point {
            maxPoint = point
        }
        return
    }
    
    for horseIdx in 0..<4 where horses[horseIdx] != (4, 4) {
        let horse = horses[horseIdx]
            
        let (nextHorse, getPoint) = move(horses[horseIdx], jump: dice[turn])
        var canMove = true
        for check in 0..<4 where horses[check] != (4, 4) && check != horseIdx {
            if horses[check] == nextHorse {
                canMove = false
                break
            }
        }
        if canMove {
            horses[horseIdx] = nextHorse
            play(turn+1, point + getPoint)
            horses[horseIdx] = horse
        }
    }
}

 

 

해결방법

var root = [[Int]](repeating: [Int](), count: 5)
root[0] = (0...19).map { $0 * 2 }
root[1] = [0, 13, 16, 19]
root[2] = [0, 22, 24]
root[3] = [0, 28, 27, 26]
root[4] = [25, 30, 35, 40, 0]

typealias Horse = (root: Int, position: Int)
var horses = [Horse](repeating: (0, 0), count: 4)

let dice = readLine()!.split(separator: " ").map { Int(String($0))! }

var maxPoint = 0

func move(_ horse: Horse, jump: Int) -> (Horse, Int) {
    switch horse.root {
        case 0:
            let nextPosition = horse.position + jump
            
            if nextPosition > 20 {
                return ((4, 4), 0)
            } else if nextPosition == 20 {
                return ((4, 3), 40)
            } else if root[0][nextPosition] == 10 {
                return ((1, 0), root[0][nextPosition])
            } else if root[0][nextPosition] == 20 {
                return ((2, 0), root[0][nextPosition])
            } else if root[0][nextPosition] == 30 {
                return ((3, 0), root[0][nextPosition])
            } else {
                return ((0, nextPosition), root[0][nextPosition])
            }
        case 1:
            if horse.position + jump > 3 {
                return ((4, horse.position + jump - 4), root[4][horse.position + jump - 4])
            } else {
                return ((1, horse.position + jump), root[1][horse.position + jump])
            }
        case 2:
            if horse.position + jump > 2 {
                return ((4, horse.position + jump - 3), root[4][horse.position + jump - 3])
            } else {
                return ((2, horse.position + jump), root[2][horse.position + jump])
            }
        case 3:
            if horse.position + jump > 3 {
                return ((4, horse.position + jump - 4), root[4][horse.position + jump - 4])
            } else {
                return ((3, horse.position + jump), root[3][horse.position + jump])
            }
        case 4:
            let nextPosition = min(4, horse.position + jump)
            return ((4, nextPosition), root[4][nextPosition])
        default:
            fatalError("invalid root")
    }
}

func play(_ turn: Int, _ point: Int) {
    guard turn < 10 else {
        if maxPoint < point {
            maxPoint = point
        }
        return
    }
    
    for horseIdx in 0..<4 where horses[horseIdx] != (4, 4) {
        let horse = horses[horseIdx]
            
        let (nextHorse, getPoint) = move(horses[horseIdx], jump: dice[turn])
        var canMove = true
        for check in 0..<4 where horses[check] != (4, 4) && check != horseIdx {
            if horses[check] == nextHorse {
                canMove = false
                break
            }
        }
        if canMove {
            horses[horseIdx] = nextHorse
            play(turn+1, point + getPoint)
            horses[horseIdx] = horse
        }
    }
}

play(0, 0)
print(maxPoint)

 

배운점

아이고 되다....