[프로그래머스] 92345 사라지는 발판 2022 KAKAO BLIND RECRUITMENT

dx = [-1,0,1,0]
dy = [0,1,0,-1]
N,M =0,0
def B_turn(curboard,A,B,turn):
    x,y = B 
    if curboard[x][y] == 0:
        return (-1,turn)
    flag = False
    winner = []
    loser = []
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0<=nx<N and 0<=ny<M:
            if curboard[nx][ny] == 1:
                new_board = [row[:] for row in curboard]
                new_board[x][y] = 0
                iswin,new_turn = A_turn(new_board,A,(nx,ny),turn+1)
                if iswin == -1:
                    winner.append(new_turn)
                else:
                    loser.append(new_turn)
                flag = True
    if flag:
        if winner:
            return (1,min(winner))
        else:
            return (-1,max(loser))
    else:
        return (-1,turn)
def A_turn(curboard,A,B,turn):
    x,y = A 
    if curboard[x][y] == 0:
        return (-1,turn)
    flag = False
    winner = []
    loser = []
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0<=nx<N and 0<=ny<M:
            if curboard[nx][ny] == 1:
                new_board = [row[:] for row in curboard]
                new_board[x][y] = 0
                iswin,new_turn = B_turn(new_board,(nx,ny),B,turn+1)
                if iswin == -1:
                    winner.append(new_turn)
                else:
                    loser.append(new_turn)
                flag = True
    if flag:
        if winner:
            return (1,min(winner))
        else:
            return (-1,max(loser))
    else:
        return (-1,turn)

def solution(board, aloc, bloc):
    global N,M
    N = len(board)
    M = len(board[0])


    return A_turn(board,aloc,bloc,0)[1]

 

 작년 카카오 마지막 문제로, 풀지 못했던 문제였다.

 

비슷하게 접근을 했지만, 원하는 정답을 구하지 못했고,

 

문제가 나오자마자 풀었다.

 

비슷한 느낌의 문제는 https://www.acmicpc.net/problem/16571

16571번: 알파 틱택토

위의 문제이고,

 

이 문제에서도, 완전탐색을 통해, 자신이 지는지, 이기는지를 판별을 하고,

 

자신이 이길 가능성이 있으면, 이길때의 최소 턴을 return 해주고,

 

전부 질때에는 최대 turn을 반환을 해주면 되는 것이다.

 

이 문제에서 지는 조건은 총 2가지로,

 

4방향으로 움직이고자할때, 움직이지 못하면, 지는 것이고,

 

두번째는 움직이고자할때, 내가 밟고 있는 발판이 사라진 상태이면 지는 것이다.

 

이 문제를 풀때,

 

예를 들어 현재 사용자(A)가 진다고 생각했을때 나는 -1과 turn을 반환을 해주었다.

 

그러면 상대방(B) 입장에서는 이 값을 return 되었을때 -1이 오게 되면, 자신이 이기게 되는 것이다.

 

그러므로, winner라는 리스트에 턴 값을 저장을 해주었다.

 

결국에는 두 사용자는 하나는 패배하게 될것이고, 한 사용자는 이기게 될것이다.

 

그래서 이기게 된 사용자는 1을 반환을 하게 만들었고,

 

이 값을 받은 입장에서는 자신의 패배가 되는 것이다.

 

그러면 X라는 턴에서 한 사용자가 모든 경우를 다 탐색하게 되면, 1 또는 -1을 받게 되어, 자신이 이기게 될지, 지게 될지를 알게 될것이다.

 

문제에서 우리는 두 사용자는 이기게 되도록 수를 둔다고 했으니, 받는 값 중에서 이기게 되는 경우가 단 1번이라도 있게 되면,

1 과 이길수 있는 경우 중에 최소 턴을 반환한다.

 

그러나 모든 경우에도 자신이 지게 되는게 확정적이라 생각되면, 최대 turn을 반환해주면 된다.

 

그래서 -1과 지는 경우 중에서 최대 턴을 반환해주도록 하도록 함수를 짜주면 된다.

 

이렇게 함수를 짜놓고, 재귀를 돌리게 되면, 문제를 해결 할 수 있는 문제였다.

 

실전에서 문제를 푸는데 틀린 이유 중 하나는, 현재 위치에서 지는 경우에 대해서 탐색을 하고, return을 해줘야하는데, 

 

최선의 수를 두지 않는, 미래의 수를 계산을 해서 return을 해줘서 틀렸던 문제였다.

 

실전에서 이 문제에 시간을 오래 소비해서 결국 6번도 풀지 못한거 보면, 문제를 해결할 때, 시간 분배를 잘해야겠다.