17825번: 주사위 윷놀이 / gold 2 / 백트래킹

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

17825번: 주사위 윷놀이

'''
17825번: 주사위 윷놀이 / gold 2 / 백트래킹
'''


# 말 위치에 따라 게임판 경로 전환하는 함수
def check_change_board(i, horse):
    # 5, 10, 15 지점일때, board (0) -> board (1) (2) (3)
    if horse[i][0] == 0:
        if horse[i][1] == 5:
            horse[i][0], horse[i][1] = 1, 0
        elif horse[i][1] == 10:
            horse[i][0], horse[i][1] = 2, 0
        elif horse[i][1] == 15:
            horse[i][0], horse[i][1] = 3, 0
        return
    # 25 중간 지점 거치면, / board (2)(3) 번 -> (1)번으로 change
    elif horse[i][0] == 2 and 3 <= horse[i][1] <= 5:
        horse[i][0], horse[i][1] = 1, horse[i][1] + 1
    elif horse[i][0] == 3 and 4 <= horse[i][1] <= 6:
        horse[i][0], horse[i][1] = 1, horse[i][1]
    # 40 위치에 도달 했을 시 -> board (0)
    elif len(board[horse[i][0]]) - 1 == horse[i][1]:
        horse[i][0] = 0
        horse[i][1] = len(board[horse[i][0]]) - 1


# 말 4개를 10턴 만큼 백트래킹하는 함수
def backtracking(depth, score, horse):
    global all_res
    # 종료 조건
    if depth == 10:
        all_res.append(score)
        return
    move = turn[depth]
    for i in range(4):
        # i번째 말 게임 판에 없고, 나가있으면 다른 말 선택
        if horse[i][1] >= len(board[horse[i][0]]):
            continue
        # i번째 말 움직이기
        pre_horse = [horse[i][0], horse[i][1]]
        horse[i][1] += move
        check_change_board(i, horse)
        # 움직인 말이 다른 말과 충돌나는지 확인
        collision = False
        # 게임 판 안에 있을 시,
        if len(board[horse[i][0]]) > horse[i][1]:
            for j in range(4):
                if i != j and horse[i][0] == horse[j][0] and horse[i][
                        1] == horse[j][1]:
                    collision = True
        # 충돌 발생 시, 제자리 위치로 + 다음 말
        if collision == True:
            horse[i][0], horse[i][1] = pre_horse[0], pre_horse[1]
        # 충돌 발생하지 않으면
        else:
            # 움직인 말이 게임판 안에 있을 시 score 추가,
            if len(board[horse[i][0]]) > horse[i][1]:
                score += board[horse[i][0]][horse[i][1]]
            # 백트래킹
            backtracking(depth + 1, score, horse)
            # 다시 원위치
            if len(board[horse[i][0]]) > horse[i][1]:
                score -= board[horse[i][0]][horse[i][1]]
            horse[i][0], horse[i][1] = pre_horse[0], pre_horse[1]


# 10턴 입력받기
turn = list(map(int, input().split()))
# 게임판 리스트
board = [[] for _ in range(4)]
board[0] = [i * 2 for i in range(21)]
board[1] = [10, 13, 16, 19, 25, 30, 35, 40]
board[2] = [20, 22, 24, 25, 30, 35, 40]
board[3] = [30, 28, 27, 26, 25, 30, 35, 40]
# 말 위치 정보
horse = [[0, 0], [0, 0], [0, 0], [0, 0]]
# 모두 나온 점수 결과
all_res = []
# 백트래킹 실행
backtracking(0, 0, horse)
# 나온 점수 결과 중 최댓값 출력
print(max(all_res))

코드 리뷰

- 문제를 푸는데 약 2시간 소요되었습니다. (목표한 시간보다 30분 초과)

- 틀린 부분을 계속 알게 되고 고치는 과정을 5번 반복 해서 최종적으로 정답 판정을 받게 되었습니다.

 

(로직 - 백트래킹)

- 전체적인 로직은 백트래킹을 통해서 10턴 동안 각 4개의 말들을 한번씩 움직이면서 (최대 4^10) 결과값을 도출하도록 구현했습니다.

(말 이동 - 시뮬레이션)

- 각 말의 위치를 이동하는 과정의 시뮬레이션에서는 게임판에서 말이 지름길?로 가는 경우, board[1], board[2], board[3]의 경로로 변경을 해주었습니다.

- 시뮬레이션에 중에서 여러 중요 예외처리를 해주어야 합니다. 

  (1) 지점 '10', '20', '30' 에서는 board[0] 경로를 -> board[1] or board[2] or board[3] 경로로 바꿔주었습니다. 

  (2) 윷놀이 판 '25' -> '40' 안의 지점은 지름길 board[1], board[2], board[3] 세가지 경로가 모두 거쳐가는 곳이기에, 해당 지점을 밟은 board[2], board[3]을 board[1]로 다시 전환하기,

  (3) 40 지점은 board[0], board[1], board[2], board[3] 모두 거쳐가는 곳이기에, 해당 지점은 board[0]으로 전환하기

  (4) 이동을 해서 방금 게임판을 나간 말이나, 이미 게임판을 나간 말들을 어떻게 할지 고민해야 합니다. (게임에 영향을 주지 말아야 함)