문제 설명
•
두 플레이어가 번갈아가며 보드에서 이동하고 최적의 전략으로 승패를 가르는 게임에서, 두 캐릭터가 움직인 총 횟수를 구하는 문제
•
게임 패배 조건은 2가지
1.
움직일 차례인데 캐릭터의 상하좌우 주변 4칸이 모두 발판이 없거나 보드 밖으로 이동할 수 없는 경우 패배
2.
두 캐릭터가 같은 발판 위에 있을 때, 상대 플레이어의 캐릭터가 다른 발판으로 이동하여 자신의 캐릭터가 서있던 발판이 모두 사라지게 되면 패배
예제 입력/출력
board | aloc | bloc | result |
[[1, 1, 1], [1, 1, 1], [1, 1, 1]] | [1, 0] | [1, 2] | 5 |
[[1, 1, 1], [1, 0, 1], [1, 1, 1]] | [1, 0] | [1, 2] | 4 |
[[1, 1, 1, 1, 1]] | [0, 0] | [0, 4] | 4 |
[[1]] | [0, 0] | [0, 0] | 0 |
제약 조건
•
문제 풀이
풀이1 브루트 포스 -
풀이 코드
from copy import deepcopy
dy = [-1, 0, 1, 0]
dx = [0, 1, 0, -1]
def in_range(y, x):
global R, C
return (0 <= y < R and 0 <= x < C)
def func(board, cury, curx, opy, opx): # 현재 상태에서 최적의 게임을 했을 때 (결과, 최대 이동횟수)
global R, C
# base case
if not in_range(cury, curx) or board[cury][curx] == 0:
return (False, 0)
if not in_range(opy, opx) or board[opy][opx] == 0:
return (True, 0)
cnt = 0
for i in range(4):
ny = cury + dy[i]
nx = curx + dx[i]
cnt += (not in_range(ny, nx) or board[ny][nx] == 0)
if cnt == 4:
return (False, 0)
# recursive case
cboard = deepcopy(board)
cboard[cury][curx] = 0
win_case = []
lose_case = []
for i in range(4):
ny = cury + dy[i]
nx = curx + dx[i]
nres, ncnt = func(cboard, opy, opx, ny, nx)
if nres == False:
win_case.append(ncnt)
else:
lose_case.append(ncnt)
if win_case: # 이기는 경우가 있다면, 최대한 빨리 이겨야 함.
return (True, min(win_case) + 1)
else: # 이기는 경우가 없다면, 최대한 오래 버티도록 해야 함.
return (False, max(lose_case) + 1)
def solution(board, aloc, bloc):
global R, C
R = len(board)
C = len(board[0])
return func(board, *aloc, *bloc)[1]
Python
복사
심화 내용
게임 이론 문제