[99클럽 코테 스터디 35일차 TIL] 주사위 윷놀이 - 백준 17825

마지막 날이다. 마지막 문제의 키워드는 시뮬레이션(구현)이다.

대신 DFS로 백트랙킹 해야한다.

 

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

주사위 윷놀이는 다음과 같은 게임판에서 하는 게임이다. (아래 그림 참조)
- 처음에는 시작 칸에 말 4개가 있다.
- 말은 게임판에 그려진 화살표의 방향대로만 이동할 수 있다. 말이 파란색 칸에서 이동을 시작하면 파란색 화살표를 타야 하고, 이동하는 도중이거나 파란색이 아닌 칸에서 이동을 시작하면 빨간색 화살표를 타야 한다. 말이 도착 칸으로 이동하면 주사위에 나온 수와 관계 없이 이동을 마친다.
- 게임은 10개의 턴으로 이루어진다. 매 턴마다 1부터 5까지 한 면에 하나씩 적혀있는 5면체 주사위를 굴리고, 도착 칸에 있지 않은 말을 하나 골라 주사위에 나온 수만큼 이동시킨다.
- 말이 이동을 마치는 칸에 다른 말이 있으면 그 말은 고를 수 없다. 단, 이동을 마치는 칸이 도착 칸이면 고를 수 있다.
- 말이 이동을 마칠 때마다 칸에 적혀있는 수가 점수에 추가된다.
주사위에서 나올 수 10개를 미리 알고 있을 때, 얻을 수 있는 점수의 최댓값을 구해보자.

[입력]
첫째 줄에 주사위에서 나올 수 10개가 순서대로 주어진다.

[출력]
얻을 수 있는 점수의 최댓값을 출력한다.

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

풀이 접근

감이 안잡혔다.

점수가 같은 칸이 있기 때문에 점수로 이동할 수도 없기에 고민을 좀 했다.

일단 각 칸마다 인덱스를 지정해줬다.

이후 각 칸에 맞는 점수를 배열로 정의했다.

var point: [Int] = [
    0, 2, 4, 6, 8, 10, 12, 14, 16, 18, // 9
    20, 22, 24, 26, 28, 30, 32, 34, 36, 38, // 19
    40, 13, 16, 19, 22, 24, 28, 27, 26, 25, // 29
    30, 35, 0
]

예를 들어 점수가 20인 칸의 인덱스는 10이니, 인덱스 10에 20 값을 저장한다.

 

다음 칸을 알기 위한 배열도 똑같이 만들었다.

대신 교차로에서 출발할 경우, 파란색 화살표를 따라가야하는 경우가 있기 때문에 이는 Dictionary를 이용했다.

let scross: [Int: Int] = [5: 21, 10: 24, 15: 26]
var destinations: [Int] = [
    1, 2, 3, 4, 5, 6, 7, 8, 9, 10, // 9
    11, 12, 13, 14, 15, 16, 17, 18, 19, 20, // 19
    32, 22, 23, 29, 25, 29, 27, 28, 29, 30, // 29
    31, 20, 32
]

예를 들어 23번 칸의 다음칸은 29이다. 그래서 배열의 23번째에는 29 값을 넣어준다.

그리고 만약 출발할때 딕셔너리에서 출발하는 칸의 값으로 다음 칸의 값을 가져올 수 있다면

destinations의 값이 아닌 가져온 값을 사용할 것이다.

 

이제 주사위 4개와 결과 값을 준비한다.

var dicePos: [Int] = [0, 0, 0, 0]
var result = 0

 

DFS를 이용해서 탐색한다.

결국 10번 움직일 수 있다.

주사위를 1 -> 1 -> 1 -> 1 ... 순서로 10번 움직일 수도 있고, 1 -> 2 -> 1 -> 3 ... 순서로 움직일 수도 있다.

이러한 로직으로 DFS 함수를 작성해보자.

func dfs(t: Int, sum: Int) {
    // 다 끝났을 때 값 갱신
    if t == 10 {
        result = max(result, sum)
        return
    }
    // 주사위 4개 순서대로 돌기
    for j in 0..<dicePos.count {
        var s = dicePos[j]
        var c = destinations[s]
        // 만약 교차로에서 파란색 화살표로 갈 수 있는 값이 있다면 해당 값을 반영
        if let cross = scross[s] {
            c = cross
        }
        // 가야하는 남은 칸 만큼 가기
        for _ in 1..<dice[t] {
            c = destinations[c]
        }
        // 도착 지점이거나 같은 칸이 아니라면 다음 dfs 탐색 시도
        if c == 32 || !dicePos.contains(c) {
            dicePos[j] = c
            dfs(t: t + 1, sum: sum + point[c])
            dicePos[j] = s
        }
    }
}

최종 코드 - Swift

var dice = readLine()!
    .split(separator: " ")
    .compactMap(String.init)
    .compactMap(Int.init)
let scross: [Int: Int] = [5: 21, 10: 24, 15: 26]
var point: [Int] = [
    0, 2, 4, 6, 8, 10, 12, 14, 16, 18, // 9
    20, 22, 24, 26, 28, 30, 32, 34, 36, 38, // 19
    40, 13, 16, 19, 22, 24, 28, 27, 26, 25, // 29
    30, 35, 0
]
var destinations: [Int] = [
    1, 2, 3, 4, 5, 6, 7, 8, 9, 10, // 9
    11, 12, 13, 14, 15, 16, 17, 18, 19, 20, // 19
    32, 22, 23, 29, 25, 29, 27, 28, 29, 30, // 29
    31, 20, 32
]
var dicePos: [Int] = [0, 0, 0, 0]

var result = 0
func dfs(t: Int, sum: Int) {
    if t == 10 {
        result = max(result, sum)
        return
    }
    for j in 0..<dicePos.count {
        var s = dicePos[j]
        var c = destinations[s]
        if let cross = scross[s] {
            c = cross
        }
        for _ in 1..<dice[t] {
            c = destinations[c]
        }
        if c == 32 || !dicePos.contains(c) {
            dicePos[j] = c
            dfs(t: t + 1, sum: sum + point[c])
            dicePos[j] = s
        }
    }
}
dfs(t: 0, sum: 0)
print(result)

Conclusion

마지막 날이라 그런지 구현과 DFS가 섞인 문제가 나온듯하다.

한달 동안 재밌게 스터디를 진행했다.