[프로그래머스] 사라지는 발판 - python

사라지는 발판

문제

각 플레이어는 자신의 캐릭터 하나를 보드 위에 올려놓고 게임을 시작합니다. 게임 보드는 1x1 크기 정사각 격자로 이루어져 있으며, 보드 안에는 발판이 있는 부분과 없는 부분이 있습니다. 발판이 있는 곳에만 캐릭터가 서있을 수 있으며, 처음 캐릭터를 올려놓는 곳은 항상 발판이 있는 곳입니다. 캐릭터는 발판이 있는 곳으로만 이동할 수 있으며, 보드 밖으로 이동할 수 없습니다. 밟고 있던 발판은 그 위에 있던 캐릭터가 다른 곳으로 이동하여 다른 발판을 밞음과 동시에 사라집니다. 양 플레이어는 번갈아가며 자기 차례에 자신의 캐릭터를 상하좌우로 인접한 4개의 칸 중에서 발판이 있는 칸으로 옮겨야 합니다.

다음과 같은 2가지 상황에서 패자와 승자가 정해지며, 게임이 종료됩니다.

• 움직일 차례인데 캐릭터의 상하좌우 주변 4칸이 모두 발판이 없거나 보드 밖이라서 이동할 수 없는 경우, 해당 차례 플레이어는 패배합니다.
• 두 캐릭터가 같은 발판 위에 있을 때, 상대 플레이어의 캐릭터가 다른 발판으로 이동하여 자신의 캐릭터가 서있던 발판이 사라지게 되면 패배합니다.

게임 보드의 초기 상태를 나타내는 2차원 정수 배열 board와 플레이어 A의 캐릭터 초기 위치를 나타내는 정수 배열 aloc, 플레이어 B의 캐릭터 초기 위치를 나타내는 정수 배열 bloc이 매개변수로 주어집니다. 양 플레이어가 최적의 플레이를 했을 때, 두 캐릭터가 움직인 횟수의 합을 return 하도록 solution 함수를 완성해주세요.

제한사항

• 1 ≤ board의 세로 길이 ≤ 5
• 1 ≤ board의 가로 길이 ≤ 5
• board의 원소는 0 또는 1입니다.
  • 0은 발판이 없음을, 1은 발판이 있음을 나타냅니다.
  • 게임 보드의 좌측 상단 좌표는 (0, 0), 우측 하단 좌표는 (board의 세로 길이 - 1, board의 가로 길이 - 1)입니다.
• aloc과 bloc은 각각 플레이어 A의 캐릭터와 플레이어 B의 캐릭터 초기 위치를 나타내는 좌표값이며 [r, c] 형태입니다.
  • r은 몇 번째 행인지를 나타냅니다.
  • 0 ≤ r < board의 세로 길이
  • c는 몇 번째 열인지를 나타냅니다.
  • 0 ≤ c < board의 가로 길이
  • 초기 보드의 aloc과 bloc 위치는 항상 발판이 있는 곳입니다.
  • aloc과 bloc이 같을 수 있습니다.
• 상대 플레이어의 캐릭터가 있는 칸으로 이동할 수 있습니다.

풀이

완탐 백트래킹 문제인데 미니맥스 알고리즘과 비슷하다고 한다.

카카오 해설과 다른 사람 풀이를 참고했다.

항상 이기는 플레이어 항상 지는 플레이어?

A의 승패 여부와 플레이어의 총 이동 횟수를 반환하는 함수

B의 승패여부와 플레이어의 총 이동 횟수를 반환하는 함수

• 상하좌우 중 가능한 곳으로 이동하여 게임판 상태 바꾸기
• 해당 상태를 상대 플레이어에게 넘기기

A 함수 : B 함수 호출

B함수 : A 함수 호출

상대 함수의 호출 결과를 통해 상대의 승패 여부와 총 이동 횟수를 알 수 있다.

상대 턴으로 넘어간 모든 함수의 결과가 승리일 경우

=> 나는 무조건 진다.

상대 턴으로 넘어간 모든 함수의 결과가 패배일 경우

=> 나는 무조건 이긴다.

함수를 호출한 결과를 종합해 이길 수 있는 방법이 있는지, 질 수 밖에 없는지를 구할 수 있다.

최적의 플레이

승리하는 플레이어 : 최소한의 이동으로 승리

패배하는 플레이어 : 최대한의 이동으로 패배

이동 횟수의 최댓값 또는 최솟값을 상대방의 결과에 따라 적절하게 반환해줘야함

1. A, B 함수 구현하기
2. A 함수 호출하기
   1. 내부에서 B함수 호출
   2. B 함수 내부에서 A 호출
3. 초기 매개변수들을 전달한 A 함수의 결과로 최적의 이동 횟수가 반환됨

def a_move(aloc, bloc, cnt, board):
    global dirs, n, m
    ax, ay = aloc
    
    if board[ax][ay] == 0:
        return (True, cnt)
    
    winner = []
    loser = []
    
    flag = False
    for dx, dy in dirs:
        nx, ny = ax + dx, ay + dy
        if 0 <= nx < n and 0 <= ny < m and board[nx][ny] == 1:
            flag = True
            temp = [row[:] for row in board]
            temp[ax][ay] = 0
            is_win, turn = b_move(bloc, [nx, ny], cnt + 1, temp)
            if is_win:
                winner.append(turn)
            else:
                loser.append(turn)
    
    if flag:
        if winner:
            return (False, min(winner))
        else:
            return (True, max(loser))
    else:
        return (True, cnt)
​
def b_move(bloc, aloc, cnt, board):
    global dirs, n, m
    ax, ay = aloc
    bx, by = bloc
    
    if board[bx][by] == 0:
        return (True, cnt)
    
    winner = []
    loser = []
    
    flag = False
    for dx, dy in dirs:
        nx, ny = bx + dx, by + dy
        if 0 <= nx < n and 0 <= ny < m and board[nx][ny] == 1:
            flag = True
            temp = [row[:] for row in board]
            temp[bx][by] = 0
            is_win, turn = a_move(aloc, [nx, ny], cnt + 1, temp)
            if is_win:
                winner.append(turn)
            else:
                loser.append(turn)
    
    if flag:
        if winner:
            return (False, min(winner))
        else:
            return (True, max(loser))
    else:
        return (True, cnt)
    
def solution(board, aloc, bloc):
    global dirs, n, m
    n = len(board)
    m = len(board[0])
    dirs = [(1, 0), (0, -1), (-1, 0), (0, 1)]
    answer = a_move(aloc, bloc, 0, board)[1]
    return answer

어우 너무 어렵다 ..