[프로그래머스]사라지는 벌판

[53] 사라지는 발판

책 구매하기

문제 정보

• 분류: 백트래킹
• 정답률: 12%
• 권장 시간 복잡도: O(2^T)
• 핵심 키워드: 게임 이론, 재귀, 승패 판단, 최소/최대 턴
• 문제링크: https://school.programmers.co.kr/learn/courses/30/lessons/92345

문제를 읽을 때 체크할 포인트

누가 이기느냐만 보는 문제가 아니라, 이길 수 있다면 최소 턴, 질 수밖에 없다면 최대 턴을 골라야 하는 게임 이론 문제다. 재귀 함수의 반환값에 승패와 턴 수를 함께 담아야 한다.

한 번의 선택으로 답이 확정되지 않고, 가능한 경우를 조건에 맞게 잘라 가며 끝까지 봐야 하는 유형이다. 그래서 '무엇을 상태로 들고 갈지'를 먼저 정하는 게 중요하다.

풀이 흐름

1. 현재 차례 플레이어가 움직일 수 있는 칸을 모두 시도한다.
2. 이동한 뒤 상대 결과를 재귀로 받는다.
3. 상대가 지는 수가 하나라도 있으면 그중 턴 수가 가장 작은 것을, 전부 지는 수뿐이면 가장 오래 버티는 수를 고른다.

구현할 때 놓치기 쉬운 부분

한 사람이 유리한 수를 고르면 다른 사람은 그 수를 최소화하려고 움직인다. 단순히 이동 횟수를 세는 DFS가 아니라 현재 턴 기준의 승패를 함께 해석해야 한다.

파이썬 정답 코드

def solution(board, aloc, bloc):
  # 현재 차례 플레이어가 움직일 수 있는 칸을 모두 시도한다.
  rows, cols = len(board), len(board[0])

  def play(a_r, a_c, b_r, b_c):
    if board[a_r][a_c] == 0:
      return False, 0

    can_move = False
    win_turn = float('inf')
    lose_turn = 0

    for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
      nr, nc = a_r + dr, a_c + dc
      if 0 <= nr < rows and 0 <= nc < cols and board[nr][nc] == 1:
        can_move = True
        board[a_r][a_c] = 0
        opponent_win, turns = play(b_r, b_c, nr, nc)
        board[a_r][a_c] = 1

        if not opponent_win:
          win_turn = min(win_turn, turns + 1)
        else:
          lose_turn = max(lose_turn, turns + 1)

    if not can_move:
      return False, 0
    if win_turn != float('inf'):
      return True, win_turn
    return False, lose_turn

  # 이동한 뒤 상대 결과를 재귀로 받는다.
  return play(aloc[0], aloc[1], bloc[0], bloc[1])[1]

시간 복잡도

T는 게임 중 실제로 밟히는 발판 상태 수이다.

발판이 사라지느냐 남아 있느냐가 상태를 만들기 때문에 실제로 밟히는 칸 수 T에 따라 상태 수가 갈린다. 각 상태에서 분기가 생기므로 최악의 경우 O(2^T)로 본다.

따라서 시간 복잡도는 O(2^T)이다.