Programming/Algorithm & Data Structure
[Swift] 백준 주사위 윷놀이 17825
guswlsdk
2024. 12. 10. 15:51
반응형
https://www.acmicpc.net/problem/17825
1. 문제이해
- 시작 칸에 말 4개
- 말은 화살표 방향대로만 이동 가능
- 말이 파란색 칸에서 이동을 시작할 경우에는 파란색 화살표로만 이동 가능
- A 말이 주사위 값 만큼 이동해야 할 곳에 다른 말이 있다면 A 말은 이동 불가, 도착점일 경우엔 상관 없음
- 말이 이동을 마칠 때마다 칸에 적혀있는 수가 점수에 추가됨
- 게임은 총 10개의 턴(10개의 주사위)만큼 이루어지고, 입력으로 주사위에서 나올 수 10개가 주어짐
- 얻을 수 있는 점수의 최댓값을 구하라.
2. 접근방법
- 입력으로 발판에 대한 입력이 주어지지 않아 발판에 대한 구조를 설계해야 함
- 배열 형식에서의 최댓값을 구하라 = dfs, 완전탐색, 백트래킹
- 어떠한 자료구조로 말이 이동하도록 할 것인가?
- 중복된 점수가 있기 때문에 칸에 적힌 점수로 인덱스를 구분하는 것은 불가능
- 발판과 점수를 각각 저장해야 함
3. 설계
- 점수 배열
- 현재 위치에서 다음 칸으로 이동할 수 있는 발판의 위치 배열
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()
반응형