17825번 - 주사위 윷놀이

문제

17825번: 주사위 윷놀이 (acmicpc.net)

17825번: 주사위 윷놀이

풀이 1

문제에서, 같은 칸에 동시에 여러개의 말이 중복해서 존재할 수 없다는 조건이 있다. 즉 말을 이동하기 전, 해당 말이 이미 도착했는지, 혹은 해당 말이 이동하려는 칸이 이미 점유 중인지 따져봐야한다.

 

말이 도착할 수 있는 칸의 종류는 총 세가지 이다. 첫째로 도착칸을 지나간 경우, 둘째로 일반칸에 도착하는 경우, 셋째로 파란칸에 도착하는 경우이다. 파란칸에 도착하는 경우 진행방향이 바뀌는 점을 유의해야한다.

 

말이 진행할 수 있는 루트는 총 네가지로 볼 수 있다.

• 시작 -> 일반 -> 도착
• 시작 -> 10 -> 도착
• 시작 -> 20 -> 도착
• 시작 -> 30 -> 도착

 

위 조건을 유의하며 윷놀이 판을 구현하면 되며, 여러 루트로 도달 가능한 칸을 딕셔너리의 키로 생각하면 된다. 말을 움직이는 경우 중 가장 결과값이 큰 경우를 구하게 될 것이므로, 백트래킹으로 접근하면 된다. 결국 윷놀이 판을 구현하는 것이 핵심인 문제였다. 쉽게 보고 제한 조건을 자세히 따져보지 않은채 문제를 접근하면 꼬이기 쉬운 유형이라고 생각된다.

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

board = {
    0: [i*2 for i in range(20)],
    10: [13,16,19],
    20: [22,24],
    30: [28,27,26],
    25: [25,30,35],
    40: [40],
    -1: [0]
}
lengthList = {k:len(v) for k,v in board.items()}

pieces = [[0,0] for _ in range(4)]


def get_max_points(cnt,points):
    global answer
    if cnt == 10:
        answer = max(answer,points)
        return
    for i in range(4):
        key, idx = pieces[i]
        if key == -1:
            continue
        if key == 0 and board[key][idx] in [10,20,30]:
            next_key,next_idx = board[key][idx],-1
        else:
            next_key, next_idx = key, idx

        for j in range(dices[cnt]):
            next_idx += 1
            if next_idx >= lengthList[next_key]:
                if next_key in [10,20,30]:
                    next_key,next_idx = 25,0
                elif next_key == 40:
                    next_key,next_idx = -1,0
                    break
                else:
                    next_key,next_idx = 40,0

        # 도착 칸 이거나, 점유 중인 칸이 아니면
        if next_key == -1 or not [next_key,next_idx] in pieces:
            pieces[i][0],pieces[i][1] = next_key,next_idx
            get_max_points(cnt+1,points+board[next_key][next_idx])
            pieces[i][0],pieces[i][1] = key,idx


answer = 0
get_max_points(0,0)
print(answer)

풀이 2

주어진 그래프를 잘 구현하면 되는 문제이다.

# 길이 7
board = [
    list(range(0,40,2)), # 5:10, 10:20, 15:30
    [13,16,19],
    [22,24],
    [28,27,26],
    [25,30,35],
    [40],
    [0,0,0,0] # 도착, 아무의미 없음
]
locs = [[0,0] for _ in range(4)]
dice = list(map(int,input().split()))


def get_answer(cnt,result):
    global answer
    if cnt == 10:
        answer = max(answer,result)
        return
    for i in range(4):
        # 이미 골에 들어가있다면 스킵
        if locs[i][0] == 6:
            continue
        # 다음칸 탐색
        r,c = locs[i]
        nr,nc = r,c
        for j in range(dice[cnt]):
            if j == 0 and r == 0 and board[r][c] in [10,20,30]:
                nr, nc = board[r][c] // 10, 0
            elif nr == 0 or nr == 4:
                if nc == len(board[nr]) - 1:
                    nr, nc = 5, 0
                else:
                    nc += 1
            elif 1 <= nr <= 3:
                if nc + 1 == len(board[nr]):
                    nr, nc = 4, 0
                else:
                    nc += 1
            elif nr == 5:
                nr, nc = 6,i
            else:
                break
        # 다음칸이 점유중이면
        if [nr,nc] in locs:
            continue
        # 이동
        locs[i][0],locs[i][1] = nr,nc
        get_answer(cnt + 1, result + board[nr][nc])
        locs[i][0],locs[i][1] = r,c


answer = 0
get_answer(0,0)
print(answer)