[Swift] 백준 주사위 윷놀이 17825

https://www.acmicpc.net/problem/17825

 

 

1. 문제이해

• 시작 칸에 말 4개
• 말은 화살표 방향대로만 이동 가능
• 말이 파란색 칸에서 이동을 시작할 경우에는 파란색 화살표로만 이동 가능
• A 말이 주사위 값 만큼 이동해야 할 곳에 다른 말이 있다면 A 말은 이동 불가, 도착점일 경우엔 상관 없음
• 말이 이동을 마칠 때마다 칸에 적혀있는 수가 점수에 추가됨
• 게임은 총 10개의 턴(10개의 주사위)만큼 이루어지고, 입력으로 주사위에서 나올 수 10개가 주어짐
• 얻을 수 있는 점수의 최댓값을 구하라.

 

2. 접근방법

• 입력으로 발판에 대한 입력이 주어지지 않아 발판에 대한 구조를 설계해야 함
• 배열 형식에서의 최댓값을 구하라 = dfs, 완전탐색, 백트래킹
• 어떠한 자료구조로 말이 이동하도록 할 것인가?
  • 중복된 점수가 있기 때문에 칸에 적힌 점수로 인덱스를 구분하는 것은 불가능
  • 발판과 점수를 각각 저장해야 함

 

3. 설계

1. 점수 배열
2. 현재 위치에서 다음 칸으로 이동할 수 있는 발판의 위치 배열

 

4. 코드

func solution(){
    let dice = readLine()!.split(separator: " ").map{Int(String($0))!}
    var visited = [0, 0, 0, 0]
    var result = 0
    let score = [
        0,
        2, 4, 6, 8, 10,
        12, 14, 16, 18, 20,
        22, 24, 26, 28, 30,
        32, 34, 36, 38, 40,
        13, 16, 19, 25, 30,
        35, 22, 24, 28, 27,
        26, 0
    ]

    let map = [
        [1],[2],[3],[4],[5],
        [6,21],[7],[8],[9],[10],
        [11,27],[12],[13],[14],[15],
        [16,29],[17],[18],[19],[20],
        [32],[22],[23],[24],[25],
        [26],[20],[28],[24],[30],
        [31],[24],[32]
    ]
    
    func dfs(dept: Int, sum: Int){
        if dept == 10{
            result = max(result, sum)
            return
        }
        
        for j in 0..<4{
            let start = visited[j]
            var cur = map[start].last! // 현재 위치에서 다음 칸 
            
            
            for _ in 1..<dice[dept]{ // 주사위 수가 1보다 클 때
                cur = map[cur].first!
            }
            
            // 도착하는 곳에 다른 말이 없어야 함, 도착점이라면 가능
            if cur == 32 || !visited.contains(cur){
                visited[j] = cur
                dfs(dept: dept+1, sum: sum+score[cur])
                visited[j] = start
            }
        }
    }
    dfs(dept: 0, sum: 0)
    print(result)
}
solution()