프로그래머스 - 사라지는 발판 (python)

[카카오] 사라지는 발판

링크

코딩테스트 연습 - 사라지는 발판

[ 문제에 대한 이해 ]

• 항상 A가 먼저 게임을 시작한다.
• 유저는 상, 하, 좌, 우 4방향으로 이동이 가능하다.
• 발판이 1인 위치로만 이동이 가능하며, 다른 발판으로 이동 시, 기존에 있었던 위치의 발판은 0이된다(사라진다).
• 움직일 차례인데 캐릭터의 상하좌우 주변 4칸이 모두 발판이 없거나 보드 밖이라서 이동할 수 없는 경우, 해당 차례 플레이어는 패배한다.
• 움직일 차례인데, 상대 플레이어가 다른 발판으로 이동하여 자신의 캐릭터가 서있던 발판이 사라지면 패배한다.
• 모든 플레이어는 항상 최선의 플레이를 한다.

접근 방법

게임 이론을 따르기 때문에, A와 B는 최선의 플레이를 한다. 최선의 플레이를 한다는 것은, 누가 이기는지, 지는지가 중요하지 않고 얼마나 최선으로 턴을 이어갈 수 있는지를 구하는 것이다.

board의 최대 크기가 5 * 5이므로, 백트래킹 방식의 dfs를 이용해야 함을 추측할 수 있다.

base case는 다음과 같이 두 개의 케이스가 있다.

1. 자기 차례가 되었는데 움직일 수 있는 공간이 없다 → 패배
2. 자기 차례가 되었는데, A와 B가 같은 공간에 있다 → 승리

이렇게 러프하게 base case를 구성하고, 조건을 세부적으로 맞춰나간다.

[ base case 정의하기 ]

# 움직일 수 있는 공간이 없을 때
if is_finished(y1, x1):
    return [False, 0]

# 현재 차례인데, 같은 공간에 있을 때
if y1 == y2 and x1 == x2:
    return [True, 1]

def is_finished(board, y, x):
    for i in range(4):
        ny = y + dy[i]
        nx = x + dx[i]
        if in_range(board, ny, nx) and board[ny][nx]:
            return False
    return True
        

[ 재귀함수에 위임할 부분을 만들기]

구현 부분에서는 다음 위치를 정하고, 재귀함수로부터 반환 받은 값을 처리하여 다음 콜스택에 위임을 해주면 된다.

1. 백트래킹으로 현재 턴의 좌표를 이동시킨다.
2. 이동하고 난 뒤, 기존 위치의 발판을 0으로 바꾼다.
3. 재귀함수로부터 결과 값을 받아온다.
4. 기존 위치의 발판을 다시 1로 바꾼다.

재귀함수로부터 결과 값을 받아오면, 해당 결과값을 처리해야 한다. 다음 턴에서 누군가가 승리한다면, 현재 턴의 사람은 무조건 패배한다는 뜻이다. 반대로 다음 턴에서 누군가가 패배한다면, 현재 턴의 사람은 무조건 승리한다.

각 플레이어는 늘 최선의 플레이를 하기 때문에, 승리할 사람은 최소 턴으로 플레이 하려고 하고, 패배할 사람은 최대의 턴으로 플레이를 하려고 한다. 때문에 최솟값과 최댓값을 모두 저장하고, 내가 한번이라도 승리할 수 있다면 최솟값을, 패배할 수 밖에 없다면 최댓값을 다음 스택으로 넘겨주면 된다.

이를 함수로 표현하면 다음과 같다.

# 구현 부분
for i in range(4):
    ny = y1 + dy[i]
    nx = x1 + dx[i]
    if in_range(ny, nx) and board[ny][nx]:
        board[y1][x1] = 0
        result = solve(board, y2, x2, ny, nx)
        board[y1][x1] = 1
    
    # 다음턴에서 패배한다면 이번 턴 사람은 승리한다는 뜻이기 때문에 최솟값을 저장
    if not result[0]:
        can_win = True
        min_turn = min(min_turn, result[1])
    # 다음턴에서 승리한다면 이번 턴 사람은 패배한다는 뜻이기 때문에 최솟값을 저장
    elif not can_win:
        max_turn = max(max_turn, result[1])

모두 저장했으면, 다음 스택에 값을 넘겨주면 된다. 내가 이길 수 있다면 최솟값을, 질 수밖에 없다면 최댓값을 반환한다.

# ...
turn = min_turn if can_win else max_turn
# 다음에는 턴 수가 증가하므로
return [can_win, turn + 1]

틀린 이유

게임 이론에 대한 이해가 부족

특히 최선의 플레이를 한다는 말이 잘 이해가 가지 않았다. 처음에 이해했을 때는, 턴 수가 길 수록 최선의 플레이를 하는 것이 아닌가? 라고 생각하여, 턴 수를 가장 긴 턴으로 답을 구했었는데 계속 틀려서 다시 문제를 보니, 승리할 사람 입장에서는 최대한 짧은 턴 안에 승리하는 것이 최선의 플레이라고 했다.

문제에서 주어진 첫 번째 케이스에 대해서 짱구를 굴려보았는데, 분명히 승리하는 경우도 있고 패배하는 경우도 있는데 어떤 경우를 잡고 문제를 해결해야 하는지 잘 몰랐다. 보니까 최선이라면, 늘 한번이라도 승리한다면 승리한다고 가정하고, 그렇지 않다면 패배한다고 생각하고 문제를 해결하면 되었다.

구현력 부족

백트래킹으로 해결하는 것 같고, 해당 부분으로 잘 접근하긴 했으나, 기저 사례를 설계하는데 있어서 약간의 미스가 있었다.

기존에는 기저사례로 움직일 수 있는 공간이 더 이상 없을 때에 대해서만 잡았었다. 두 플레이어의 현재 위치가 같을 때 다음 차례에는 게임이 무조건 끝난다는 사실을 간과하고, 해당 부분은 구현 단에서 체크를 하려고 했었던 것이 코드를 복잡하게 만든 원인이라고 생각한다. 조금만 깊게 생각하면 작성할 수 있었을텐데, 사고력이 많이 부족했다.

플레이어가 다르기 때문에 각 플레이어를 처리하기 위하여 각 플레이어를 다루는 함수를 모두 구현했었으나, 두 로직이 사실상 같기 때문에 매개변수의 위치만 바꿔주면 로직을 재사용할 수 있다는 사실을 몰랐다.

그리고 기존의 코드를 짜면서 맘에 들지 않았던 부분인데, 횟수를 저장하는 cnt가 매개변수로 존재하면서 글로벌 변수에 값을 저장하는 용도로 사용된다는 사실이 맘에 들지 않았다. 그런데 이길 수 있을지, 말지를 재귀함수의 반환 값으로 받아 처리하는 부분을 보고 많이 충격을 받았다.

배운 것

[ 구조 표현하기 ]

일반적으로 a 와 b 모두 각자의 턴이 존재할 때, 같은 구조를 같이 적어야한다. 그러나 행동이 같고 턴만 다를 경우에는 매개변수의 위치만 바꿔주면 비슷한 로직을 반복할 필요가 없다.

# turn 1
solve(y1, x1, y2, x2)

# turn 2
solve(y2, x2, y1, x1)

[ count 매개변수 ]

기존 코드에서는 count를 매개변수로 쓰면서 동시에 값을 저장했었다. 그런데 결과 값으로 해당 매개변수를 이용하는 것 보다, 차라리 false일 때는 0, true일 때는 1을 반환하면서 더해가면 좀 더 깔끔하게 재귀함수를 작성할 수 있다.

통과 코드

dy = [-1, 1, 0, 0]
dx = [0, 0, -1, 1]
INF = 987654321


def solution(board, aloc, bloc):
    return solve(board, aloc[0], aloc[1], bloc[0], bloc[1])[1]


def in_range(board, y, x):
    if y < 0 or y >= len(board) or x < 0 or x >= len(board[0]):
        return False
    return True


def is_finished(board, y, x):
    for i in range(4):
        ny = y + dy[i]
        nx = x + dx[i]
        if in_range(board, ny, nx) and board[ny][nx]:
            return False
    return True


def solve(board, y1, x1, y2, x2):
    # can_win, turn
    if is_finished(board, y1, x1):
        return [False, 0]

    # 서로 두 위치가 같을 때 이번 턴에 움직이면 무조건 이기므로
    if y1 == y2 and x1 == x2:
        return [True, 1]

    min_turn = INF
    max_turn = 0
    can_win = False

    # dfs
    for i in range(4):
        ny = y1 + dy[i]
        nx = x1 + dx[i]
        if not in_range(board, ny, nx) or not board[ny][nx]:
            continue

        board[y1][x1] = 0
        result = solve(board, y2, x2, ny, nx)  # 차례가 바뀌기 때문에 위치를 바꿔준다.
        board[y2][x2] = 1

        # 이 시점에서는 result[0]이 False여야만 현재 턴에서 내가 이길 수 있다.
        if not result[0]:
            can_win = True
            min_turn = min(min_turn, result[1])
        elif not can_win:
            max_turn = max(max_turn, result[1])

    turn = min_turn if can_win else max_turn

    return [can_win, turn + 1]