2022 KAKAO BLIND RECRUITMENT 사라지는 발판 Lv. 3

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/92345

파이썬 소스: https://bit.ly/3watUuE

 

 문제를 읽다가 아래 문장을 만나면… 문제가 더 이해가 안가기 시작합니다.

양 플레이어는 최적의 플레이를 합니다. 즉, 이길 수 있는 플레이어는 최대한 빨리 승리하도록 플레이하고, 질 수밖에 없는 플레이어는 최대한 오래 버티도록 플레이합니다. '이길 수 있는 플레이어'는 실수만 하지 않는다면 항상 이기는 플레이어를 의미하며, '질 수밖에 없는 플레이어'는 최선을 다해도 상대가 실수하지 않으면 항상 질 수밖에 없는 플레이어를 의미합니다. 최대한 오래 버틴다는 것은 양 플레이어가 캐릭터를 움직이는 횟수를 최대화한다는 것을 의미합니다.

 이게 무슨 말인지…? 하는 생각이 드는 대요… 이 부분을 좀더 알아보겠습니다.

플레이어는 A, B 두명으로, A가 이기면, B는 지고, B가 이기면 A는 지는 게임입니다.

1. A 가 먼지 이동하고,

2. B 가 이동하고,

3. A 가 이동하고

4. B 가 이동 못해서 패배할 수도 있고,

이런 순서로 계속 서로 누가 먼저 패배하는 조건에 이를 때까지 반복인 것이죠.

4번에서 B 가 이동하지 못해서 패배했다고 가정해 보겠습니다.

그러면 B의 패배를 리턴 할 수 있습니다. 이문제는 이동한 거리를 구하는 문제 임으로, A와 B가 그동안 이동한 거리도 함께 리턴합니다.

그러면 3번 A의 입장에서는 B가 패배를 리턴 했으므로, A의 승리가 됩니다.

2번의 B의 입장에선 A가 승리했으므로 B의 패배가 되구요.

최종적으로 1번 A는 승리하게 됩니다.

 

앞에서는 간략하게 설명하기 위해서, 1, 2, 3, 4각 단계 마다 승리, 패배를 간략하게 설명했는대요, 이제는 실제와 같이 승리, 패배, 이동거리가 여러가지인 경우를 알아 보겠습니다.

이 문제는 A가 이동하고 B가 이동하는 형태 임으로 2개의 재귀함수가 서로를 호출하는 형태입니다. 소스에서는 a_move()함수에서 A가 한칸 이동하고, b_move()함수를 호출하게 되고, 다시 b_move()는 a_move()를 호출하게 됩니다. 이 때, A, B 중에 하나가 패배하게 되면, 패배와, 이동거리의 합을 리턴합니다. 앞에서는 4번의 B는 자신의 패배임으로, 이동거리가 가장 긴 것을 리턴합니다.

3번 a_move()는 최대 4가지 방향으로 이동이 가능합니다. 4가지 방향으로 이동했을 때, 4번의 b_move()함수가 리턴하는 B의 승리, 패배, 이동 거리는 여러가지 경우가 있습니다.

3가지 경우로 모을 수 있는대요, 1. B의 승리만 리턴, 2. B의 패배만 리턴, 3, B의 승리, 패배 모두 리턴 되는 경우입니다.

1. 모두 B의 승리만 리턴한 경우, A는 패배하는 경우 밖에 없습니다.

A의 패배를 리턴하고, 가장 이동거리가 긴 것을 리턴합니다.

2. 모두 B의 패배만 리턴한 경우, A는 승리하는 경우 밖에 없습니다.

A의 승리를 리턴하고, 가장 이동거리가 짧은 것을 리턴합니다.

3. B의 승리, 패배 2가지 리턴되는경우

A의 입장에서는 B의 승리는 모두 무시하고, B의 패배만 확인합니다.

B의 패배 중에서 가장 짧은 것을 골라서, A의 승리와 함께, 가장 짧은 길이를 리턴합니다.

 

이제 문제를 코딩해보겠습니다.

dyx = [[-1, 0], [0, 1], [1, 0], [0, -1]]

가장 먼저 전,후,좌,우로 이동하는 값 dyx부터 코딩합니다.

 

def solution(board: List[List[int]], aloc: List[int], bloc: List[int]) -> int:     answer = a_move(board, aloc[0], aloc[1], 0, bloc[0], bloc[1], 0)     return answer[1]

이동은 항상 A부터 시작 하기 때문에, a_move()함수를 호출 합니다.

a_move() 함수는 A의 승리/패배와 이동거리를 함께 리턴합니다.

이동거리만 리턴하기 때문에 answer[1]을 리턴합니다.

 

def a_move(board: List[List[int]], ay, ax, adepth, by, bx, bdepth):     if board[ay][ax] == 0:         return [False, adepth + bdepth]     loses = [adepth + bdepth]     wins = []     for dy, dx in dyx:         ny, nx = dy + ay, dx + ax         if is_movable(board, ny, nx):             new_board = copy.deepcopy(board)             new_board[ay][ax] = 0             [win, depth] = b_move(new_board, ny, nx, adepth + 1, by, bx, bdepth)             if win:                 loses.append(depth)             else:                 wins.append(depth)     if wins:         wins.sort()         return [True, wins[0]]     loses.sort(reverse=True)     return [False, loses[0]]

A와 B가 같은 위치에 있을 수도 있습니다. 이 때 B가 다른 위치로 이동 했다면, 해당 위치가 0이 되어, A는 이동할 기회도 없이 패배 하게 됩니다.

따라서, 가장 먼저 현재 A의 위치가 0인지부터 확인하고, 패배한 경우에는 False와 A, B이동 거리의 합을 리턴합니다.

 A가 이동할 수 없는 경우에도 A의 패배 이기 때문에, 패배한 경우의 이동거리를 모아두는 리스트 loses 에 현재까지 A,B 이동거리를 초기값으로 넣어 주게 됩니다.

4가지 방향으로 이동을 시도해보고, is_movable()함수로 이동 가능한 위치인지 확인하고 이동하게 됩니다. 여러 방향으로 이동해야 하기 때문에 board를 복사해서, 현재 위치를 0으로 바꾸고, b_move()함수를 호출해서 이제 B가 이동합니다.

함수 b_move()가 리턴해주는 B의 승리/패배 여부에 따라서, B가 승리했다면, A 가 졌으므로, 진경우를 모아두는 loses리스트에 이동거리를 추가합니다. B가 패배 했다면, B가 이겼으므로, 이긴 경우를 모아두는 wins리스트에 이동기를 추가합니다.

A가 승리한 경우가 한 개 이상이라면, A의 승리를 리턴합니다. A의 승리 중에서 가장 짧은 경우를 리턴하기 위해서, wins를 sort()하구요, 가장 짧은 거리인 wins[0]과 함께 A의 승리 True를 리턴합니다.

A의 승리가 없다면, 패배를 리턴합니다. 최대한 이동거리가 긴 것을 선택하기 위해서 reverse=True로 sort()를 하고, False와 함께 loses[0]을 리턴합니다.

 

함수 b_move()도 같은 방식으로 코딩할 수 있으므로 아래 전체 코드를 참고해주세요.

 

궁금한 문제, 내용은 댓글, 이메일(coding.data.pul@gmail.com)로 보내주세요.

코데풀 유튜브 구독 부탁드립니다.

https://www.youtube.com/@codapul

 

전체 코드는 아래에 있습니다.

import copy from typing import List dyx = [[-1, 0], [0, 1], [1, 0], [0, -1]] def solution(board: List[List[int]], aloc: List[int], bloc: List[int]) -> int:     answer = a_move(board, aloc[0], aloc[1], 0, bloc[0], bloc[1], 0)     return answer[1] def a_move(board: List[List[int]], ay, ax, adepth, by, bx, bdepth):     if board[ay][ax] == 0:         return [False, adepth + bdepth]     loses = [adepth + bdepth]     wins = []     for dy, dx in dyx:         ny, nx = dy + ay, dx + ax         if is_movable(board, ny, nx):             new_board = copy.deepcopy(board)             new_board[ay][ax] = 0             [win, depth] = b_move(new_board, ny, nx, adepth + 1, by, bx, bdepth)             if win:                 loses.append(depth)             else:                 wins.append(depth)     if wins:         wins.sort()         return [True, wins[0]]     loses.sort(reverse=True)     return [False, loses[0]] def b_move(board: List[List[int]], ay, ax, adepth, by, bx, bdepth):     if board[by][bx] == 0:         return [False, adepth + bdepth]     loses = [adepth + bdepth]     wins = []     for dy, dx in dyx:         ny, nx = dy + by, dx + bx         if is_movable(board, ny, nx):             new_board = copy.deepcopy(board)             new_board[by][bx] = 0             [win, depth] = a_move(new_board, ay, ax, adepth, ny, nx, bdepth + 1)             if win:                 loses.append(depth)             else:                 wins.append(depth)     if wins:         wins.sort()         return [True, wins[0]]     loses.sort(reverse=True)     return [False, loses[0]] def is_movable(board, y, x):     if 0 <= y < len(board) and 0 <= x < len(board[0]) and board[y][x] == 1:         return True     return False