[백준/Python] 17825 주사위 윷놀이

📌문제 탐색하기

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

해당 문제는 매 턴마다 4개의 말 각각을 움직일 수 있는 모든 경우의 수를 찾아 말을 움직여 가면서 얻을 수 있는 점수의 최댓값을 구해야 한다. 즉, 백트래킹을 활용한 브루트포스 탐색을 통해 답을 구할 수 있다.

 

📌 코드 설계

1. 주사위에서 나오는 숫자 10개를 numbers 리스트에 입력받는다.
2. 게임판의 정보를 저장하기 위한 game_map을 하드코딩한다.
   • 나는 게임판의 각 경로를 "특정 지점에서 시작해서 다른 경로와 겹칠 수 있는 지점까지"로 경로를 나눠 저장했다.
3. 4개의 말 현재 위치를 저장할 current_positions 리스트와 얻은 최고 점수를 기록할 high_score 변수를 생성한다.
4. 말을 이동시켰을 때 다른 말과 충돌하는지 여부를 검사할 check_collisions(moving_token, way, count)를 정의한다.
   • current_positions를 돌면서, 현재 확인 중인 말과 다른 말이 서로 위치가 동일하다면 True를 리턴하고, 아니라면 False를 리턴한다.
5. 백트래킹 알고리즘을 수행할 함수 backtracking(cur_round, score)를 정의한다.
   1. 현재 턴, 즉 cur_round가 10이면 현재까지의 점수 score를 기준으로 high_score 갱신하고 함수를 종료한다.
   2. 현재 주사위 눈이 몇인지 dice_number에 저장한다.
   3. 현재 턴 기준 4개의 말을 하나씩 움직이며 모든 경우의 수를 탐색한다.
   4. 각 말의 위치(way, count)(경로 번호, 해당 경로에서 몇번째 칸에 위치하는지)에 주사위의 눈만큼 이동시켜 game_map에서 어디에 위치해야 하는지를 (new_way, new_count)로 구한다.
   5. 계산된 new_way, new_count의 위치에 이미 말이 존재하는지 check_collisions(moving_token, new_way, new_count)를 호출해 확인한다. 이미 존재하는 위치라면 다음 말로 넘어간다.
   6. 말을 이동시키고 current_positions를 갱신후 backtracking(cur_round+1, score+이동한 칸의 숫자)를 재귀호출한다. 그 후 current_positions를 복원한다.
6. backtraking(0, 0)을 호출해 모든 경우에 대한 탐색을 수행한 후 갱신된 high_score를 출력한다.

 

📌 시도 회차 수정 사항

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

위와 같이 게임판을 0, 10, 20, 30에서 출발해서 도착지점까지의 네가지 경로로만 나누어서 하드코딩 했는데, 똑같은 칸에 대한 요소(ex. 10에서 출발해서 25 도착하는 것과 20에서 출발해서 25에 도착하는 것은 동일한 칸에 도착하는 것이지만, 위 game_map에서는 다른 요소임)가 여러 개 있어서 방문 처리를 어렵게 만들었다. 방문 처리 부분을 여러번 수정했음에도 불구하고 아래와 같은 특정 케이스에서 계속 오답이 나왔다.

2 2 2 2 2 2 2 2 2 2

기댓값
166

 

그래서 특정한 칸에 대한 표현을 하나만 가질 수 있도록, 아래와 같이 game_map을 수정하고 코드 상에서 각 경로의 끝에 도달한 경우 무조건 다른 경로로 이동시켰다. 

ex) 10에서 출발해 25를 거쳐가는 경우와 20에서 출발해 25를 거쳐가는 경우, 즉 game_map[1][4] 또는 game_map[2][3]에 도달하면 무조건 game_map[4][0]으로 이동해서 진행

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

 

📌정답 코드

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

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

current_positions = [[0,0] for _ in range(4)] # 4개의 말 각각의 위치 저장
high_score = 0

def backtracking(cur_round, score):
    global high_score
    
    if cur_round == 10:
        high_score = max(high_score, score)
        return
        
    dice_number = numbers[cur_round]
    visited_pos = []

    for moving_token in range(4):
        way, count = current_positions[moving_token]

        # 이미 확인한 위치에서 시작하려고 하면 중지
        if [way, count] in visited_pos:
            continue
        visited_pos.append([way, count])
        
        # 이미 도착한 말에 대한 처리
        if way == -1:
            continue
        
        new_way, new_count = move_token(way, count+dice_number)
        if new_way == -1 and new_count == -1:
            current_positions[moving_token] = [-1, -1]
            backtracking(cur_round + 1, score)
            current_positions[moving_token] = [way, count]
            continue

        current_score = game_map[new_way][new_count]
        
        # 파란색 칸에서 시작하는 경우 경로 변경
        if new_way == 0 and current_score in [10, 20, 30]:
            new_way = current_score // 10
            new_count = 0
        
        # 도착한 칸에 다른 말이 있는지 확인
        if check_collision(moving_token, new_way, new_count):
            continue
            
        current_positions[moving_token] = [new_way, new_count]
        backtracking(cur_round+1, score+current_score)
        current_positions[moving_token] = [way, count]

def move_token(way, count):    
    while count >= len(game_map[way]) - 1:
        if way == 5:
            return -1, -1
        
        count -= (len(game_map[way]) - 1)
        way = 5 if way in [0, 4] else 4
        
    return way, count

def check_collision(moving_token, new_way, new_count):
    for idx, (way, count) in enumerate(current_positions):
        if idx != moving_token and way == new_way and count == new_count:
            return True
    return False


backtracking(0, 0)
print(high_score)