[백트래킹] K개 중 하나를 N번 선택하기(Conditional) / 1차원 윷놀이

문제링크

https://www.codetree.ai/missions/2/problems/yutnori-1d?&utm_source=clipboard&utm_medium=text

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

1. 핵심

• 움직임의 크기가 이미 정해져있을 때 공들을 선택할 수 있는 조합을 만들고 최대 점수를 먹는 것!
  • 각 공은 1 1 1  / 1 2 1 ...이렇게 선택될 수 있다. > 중복순열
  • simple유형이라고 생각할 수 있지만 이미 m번으로 이동한 말의 경우 점수에 영향을 주지 못하고 이동횟수만 소진하게 된다.
  • 따라서 m에 도착한 말은 선택되지 않도록 경우의 수를 생성해야한다. (conditional)
• board 
  • 인덱스가 곧 공의 좌표를 의미한다.
  • 따라서 board는 1로 초기화할 수 있다. 이는 m >= 2 이므로 가능하다. m = 1 인 상황에서 1로 초기화한 경우 이동하지 못하는 문제가 발생한다.
  • 그것까지 고려해서 board는 0으로 초기화하겠다. 그러므로 도착을 판단할 때는 m이 아니라 m - 1이어야한다.
  • board에 공의 위치를 바로 기록하므로 ans 는 도입하지 않는다.
• k = 1 일 때 conditional에서 에러가 발생한 이유
  • k = 1일 경우 continue 때문에 1번 공이 m에 도착한 이후에는 continue에 의해서 level + 1이 되지 않는다. 따라서 level이 n이 되지 못해서 종료 if문에 들어오지 못한채로 백트래킹이 종료된다.
  • 따라서 n번 모두 움직이지 않아도 점수가 갱신될 수 있도록 if문 밖에서 점수를 갱신한다.
• Intution: N번의 턴에 대해 각 턴마다 K개 중 어떤 말을 움직일 것인지를 선택하는 재귀함수 작성. 이때, 이미 점수를 획득한 말을 움직이지 않는면 총 탐색 시간 감소할 수 있음.

2. 코드(Python)

[풀이1] simple - 모든 경우 전수 조사

n, m, k = map(int, input().split())
move_numbers = list(map(int, input().split()))

# board - 공의 시작점이 1부터 시작이다!
# board의 각 인덱스가 공의 좌표를 의미한다.
# 1번에서 시작하기 때문에 board의 초기값은 1로 설정하는 것이 맞다.
# 1로 설정했을 때 m 이 1인 경우 공들이 아예 못 움직이는 경우가 있다.
# 그러므로 0으로 설정하되 판단할 때 m 이 아니라 m - 1로 판단하는 것이 괜찮아 보인다.
board = [0 for _ in range(k + 1)]

# 움직임이 이미 정해져있을 때 말들을 선택할 수 있는 조합을 만들고 최대 점수를 먹는 것!
# 각 말은 1 1 1  / 1 2 1 ...이렇게 선택될 수 있다. > 중복순열
# simple유형이라고 생각할 수 있지만 이미 m번으로 이동한 말의 경우 점수에 영향을 주지 못하고 이동횟수만 소진하게 된다.
# 따라서 m에 도착한 말은 선택되지 않도록 경우의 수를 생성해야한다. (conditional)
# 중복조합 + conditional

# board에 move_number에 따른 공의 좌표를 기록한다. ans필요없음!
max_score = 0
def dfs(level):
    global max_score
    if level == n:
        sum_val = sum([1 for x in board if x >= m - 1])
        # print(f"sum_val: {sum_val}, board: {board}")
        max_score = max(max_score, sum_val)
        return
    
    for cur_dice in range(1, k + 1):
        board[cur_dice] += move_numbers[level]
        dfs(level + 1)
        board[cur_dice] -= move_numbers[level]

# k = 1일때 level == n에 안들어감...왜?

dfs(0)
print(max_score)

 

 [풀이2] conditional - m번에 도착한 말은 보지 않음.

n, m, k = map(int, input().split())
move_numbers = list(map(int, input().split()))
board = [0 for _ in range(k + 1)]

max_score = 0
def dfs(level):
    global max_score

    # level이 n까지 도달하지 못하도록 갱신시키기...
    # if level==n안에서 갱신시키면 level이 m에 도착했지만 n 레벨에 도달하지 못하면 갱신을 하지 못한다.
    # 따라서 n번 미만 움직이더라도 갱신되도록 해야한다.
    sum_val = sum([1 for x in board if x >= m - 1])
    max_score = max(max_score, sum_val)

    if level == n:
        return
    
    for cur_dice in range(1, k + 1):
        # conditional
        if board[cur_dice] >= m:
            continue
        board[cur_dice] += move_numbers[level]
        dfs(level + 1)
        board[cur_dice] -= move_numbers[level]

dfs(0)
print(max_score)