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

이렇게 생긴 윷놀이 판을 이동해서 최대 점수를 얻게하는 문제이다.

말 4개가 있고 10번의 턴이 있기 때문에 최대 4^10의 경우라서 완전탐색을 진행했다.

Python

시도 1 - 실패

nums = list(map(int, input().split()))

graph = dict()
blue = dict()

score = [
    0,
    2,
    4,
    6,
    8,
    10,
    13,
    16,
    19,
    25,
    12,
    14,
    16,
    18,
    20,
    22,
    24,
    22,
    24,
    26,
    28,
    30,
    32,
    34,
    36,
    38,
    26,
    27,
    28,
    30,
    35,
    40,
    0,
]

graph[0] = [1]
graph[1] = [2]
graph[2] = [3]
graph[3] = [4]
graph[4] = [5]
graph[5] = [10]
graph[6] = [7]
graph[7] = [8]
graph[8] = [9]
graph[9] = [29]
graph[10] = [11]
graph[11] = [12]
graph[12] = [13]
graph[13] = [14]
graph[14] = [17]
graph[15] = [16]
graph[16] = [9]
graph[17] = [18]
graph[18] = [19]
graph[19] = [20]
graph[20] = [21]
graph[21] = [22]
graph[22] = [23]
graph[23] = [24]
graph[24] = [25]
graph[25] = [31]
graph[26] = [9]
graph[27] = [26]
graph[28] = [27]
graph[29] = [30]
graph[30] = [31]
graph[31] = [32]

blue[5] = [6]
blue[14] = [15]
blue[21] = [28]

ans = 0

horses = [0, 0, 0, 0]


def move(next, count):
    while count > 0 and next != 32:
        next = graph[next][0]
        count -= 1
    return next


def backtracking(horses, idx, s):
    global ans

    if idx == 10:
        ans = max(ans, s)
        return

    for i in range(4):
        count = nums[idx]
        now = horses[i]

        if now == 32:
            continue

        next = move(now, count)

        if next not in horses or next == 32:
            horses[i] = next
            backtracking(horses, idx + 1, s + (score[next] if next != 32 else 0))
            horses[i] = now

        if now in blue:
            next = move(blue[now][0], count - 1)

            if next not in horses or next == 32:
                horses[i] = next
                backtracking(horses, idx + 1, s + (score[next] if next != 32 else 0))
                horses[i] = now


backtracking(horses, 0, 0)

print(ans)

사진처럼 번호를 부여하고, 그래프를 만든 후 백트래킹을 했다. 파란색 칸을 만나면 빨간길과 파란길 두 가지 다 탐색하도록 했다. 그리고 실패했다.

시도 2 - 실패

nums = list(map(int, input().split()))

# routes = [
#     [-1, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 34, 36, 38, 40, 0],
#     [10, 13, 16, 19, 25, 30, 35, 40, 0],
#     [20, 22, 24, 25, 30, 35, 40, 0],
#     [30, 28, 27, 26, 25, 30, 35, 40, 0],
# ]

routes = [
    [-1, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 34, 36, 38, 40, 0],
    [-1, 13, 16, 19, 25, 30, 35, 40, 0],
    [-1, 22, 24, 25, 30, 35, 40, 0],
    [-1, 28, 27, 26, 25, 30, 35, 40, 0],
]

blue = [5, 10, 15]


horse = [0, 0, 0, 0]
hr = [0, 0, 0, 0]
ans = 0


def backtracking(horse, idx, score):
    if idx == 10:
        global ans
        ans = max(ans, score)
        return

    for i in range(4):
        now = horse[i]
        route = routes[hr[i]]
        count = nums[idx]

        if route[now] == 0:
            continue
        next = min((now + count), len(route) - 1)

        chk = True
        for h in range(4):
            if i == h:
                continue
            if horse[h] == next and hr[i] == hr[h]:
                chk = False
                break
        if chk:
            horse[i] = next
            backtracking(horse, idx + 1, score + route[next])
            horse[i] = now

        if now in blue:
            original_hr = hr[i]
            r = blue.index(now) + 1
            hr[i] = r
            route = routes[hr[i]]

            chk = True
            for h in range(4):
                if i == h:
                    continue
                if horse[h] == next and hr[i] == hr[h]:
                    chk = False
                    break

            if chk:
                next = min((now + count), len(route) - 1)
                horse[i] = next
                backtracking(horse, idx + 1, score + route[next])
                horse[i] = now
            hr[i] = original_hr


backtracking(horse, 0, 0)
print(ans)

질문하기에 루트만 따로 추출해서 문제를 접근하길래 이 방식을 해보았다. 결과는 시도 1과 같았다.

시도 3

nums = list(map(int, input().split()))

graph = dict()
blue = dict()

score = [
    0,
    2,
    4,
    6,
    8,
    10,
    13,
    16,
    19,
    25,
    12,
    14,
    16,
    18,
    20,
    22,
    24,
    22,
    24,
    26,
    28,
    30,
    32,
    34,
    36,
    38,
    26,
    27,
    28,
    30,
    35,
    40,
    0,
]

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

ans = 0

horses = [0, 0, 0, 0]


def move(next, count):
    while count > 0 and next != 32:
        next = graph[next][0]
        count -= 1
    return next


def backtracking(horses, idx, s):
    global ans

    if idx == 10:
        ans = max(ans, s)
        return

    for i in range(4):
        count = nums[idx]
        now = horses[i]

        next = graph[now][-1]
        next = move(next, count - 1)

        if next not in horses or next == 32:
            nhorse = horses[:]
            nhorse[i] = next
            backtracking(nhorse, idx + 1, s + score[next])


backtracking(horses, 0, 0)

print(ans)

문제를 제대로 안 읽어서 실패한 것이었다. 파란칸이면 파란길로만 이동해야하는 조건이 있었는데 그걸 놓쳤다.

파란 칸일 때는 파란길만 가게 설정했더니 통과할 수 있었다.

---

충분히 시간 안에 풀 수 있는 문제였는데 문제를 제대로 안 읽어서 실패했다. 막히면 문제를 제대로 다시 읽는 습관을 들여야겠다.