99클럽 코테 스터디 4기 35일차 TIL - 백준: 주사위 윷놀이 (17825) Swift

ℹ️ 문제 정보

플랫폼	번호	제목	유형	난이도	언어
백준	17825	주사위 윷놀이	시뮬레이션	골드2	Swift

🚀 나의 접근 방법

이 문제는 브루트포스, 시뮬레이션, 백트래킹 관련 문제이다. 즉, 탐색을 통해 모든 경우의 수를 탐색하게 된다.

중요한 것 중 하나가 탐색에 필요한 인접 행렬을 정의하는 것이다. 문제에서 주어진 그래프가 복잡하기 때문에 꼼꼼하게 정의해야 한다.

한 가지 특징이 있다면 중간에 파란색 화살표로 분기가 가능하다는 것이다. 부분은 두 개의 방향을 하나의 리스트로 묶되 1번 인덱스는 출발 시 노드로 정의했다.

DFS로 탐색했으며 말을 하나씩 이동시켜보며 모든 경우의 수를 탐색하여 점수의 최댓값을 구했다.

✍️ 나의 코드

Swift

let adj = [[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],[32],[32],[32],[32]]
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]

func dfs(_ n: Int, _ sum: Int) {
    if n == 10 {
        ans = max(ans, sum)
        return
    }
    
    for j in 0..<4 {
        let s = v[j]
        var c = adj[s].last!
        for _ in 1..<list[n] {
            c = adj[c].first!
        }
        
        if c == 32 || !v.contains(c) {
            v[j] = c
            dfs(n+1, sum+score[c])
            v[j] = s
        }
    }
}

let list = readLine()!.split(separator: " ").map{ Int($0)! }
var v = [0, 0, 0, 0]
var ans = 0
dfs(0, 0)
print(ans)

🤔 회고

풀이를 생각하기 어려운 문제였다. 꼭 다시 한 번 풀어보자.
참고 - [삼성기출 #33] 17825. 주사위 윷놀이 (백준, 파이썬)