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

April 15, 2022

def aDfs(board, aloc, bloc, aroad, broad, N, M):
    winResult = [25, 0]
    loseResult = [0, 25]
    win = 0
    cnt = 0
    
    if board[aloc[0]][aloc[1]] == 0:
        return [aroad, broad], 1
    
    direction = [[0,1], [1, 0], [-1,0], [0,-1]]
    for dx, dy in direction:
        x, y = aloc
        if 0 <= x + dx < N and 0 <= y + dy < M and board[x+dx][y+dy] == 1:
            cnt += 1
            board[x][y] = 0
            [aResult, bResult], result = bDfs(board, [x+dx, y+dy], bloc, aroad+1, broad, N, M)
            win += result
            board[x][y] = 1
            if result == 1 and winResult[0] > aResult:
                winResult = [aResult, bResult]
            if result == 1 and winResult[0] == aResult:
                winResult = [aResult, max(winResult[1], bResult)]
            if result == 0 and loseResult[0] < aResult:
                loseResult = [aResult, bResult]
            if result == 0 and loseResult[0] == aResult:
                loseResult = [aResult, min(loseResult[1], bResult)]
                
    if cnt == 0:
        return [aroad, broad], 1
    
    if win > 0:
        return winResult, 0
    return loseResult, 1

def bDfs(board, aloc, bloc, aroad, broad, N, M):
    winResult = [0, 25]
    loseResult = [25, 0]
    win = 0
    cnt = 0
    
    if board[bloc[0]][bloc[1]] == 0:
        return [aroad, broad], 1
    
    direction = [[0,1], [1, 0], [-1,0], [0,-1]]
    for dx, dy in direction:
        x, y = bloc
        if 0 <= x + dx < N and 0 <= y + dy < M and board[x+dx][y+dy] == 1:
            cnt += 1
            board[x][y] = 0
            [aResult, bResult], result = aDfs(board, aloc,[x+dx,y+dy], aroad, broad+1, N, M)
            win += result
            board[x][y] = 1
            if result == 1 and winResult[1] > bResult:
                winResult = [aResult, bResult]
            if result == 1 and winResult[1] == bResult:
                winResult = [max(winResult[0], aResult), bResult]
                
            if result == 0 and loseResult[1] < bResult:
                loseResult = [aResult, bResult]
            if result == 0 and loseResult[1] == bResult:
                loseResult = [min(loseResult[0], aResult), bResult]
            
            
    if cnt == 0:
        return [aroad, broad], 1
    
    if win > 0:
        return winResult, 0
    return loseResult, 1

def solution(board, aloc, bloc):
    if len(board) * len(board[0]) <= 1: return 0
    if aloc == bloc: return 1
    result, win = aDfs(board, aloc, bloc, 0, 0, len(board), len(board[0]))
    return sum(result)

굉장히 쉽지 않은 문제였습니다. 뭔가 가지고 있던 생각을 고쳐먹어야 했고, 카카오 테크 블로그의 설명이 더욱 저를 헷갈리게 했습니다.(ㅋㅋ)

문제해설

가장 중요한 것은 최선의 움직임을 취한다는 말의 의미를 파악하는 것입니다.

최선의 움직임을 취한다는 것
1. 이길 수 있는 점은 무조건 간다.
2. 이긴다면 가장 적게 움직이고, 진다면 가장 많이 움직이게 한다.
저는 1번을 조금 간과하는 바람에 문제를 푸는데 좀 오랜 시간이 걸렸습니다.
더 이상 갈데가 없으면 패배한 것이다.

승리 조건을 찾는 것 보다 패배 조건을 찾는 것이 쉬우므로 리프노드에서는 패배를 리턴하게끔 설계 하였습니다.

간단하게 간추리면 위와 같지만 이길수 있는 점은 무조건 간다라는 말을 상세히 설명 해보도록 하겠습니다.

DFS 탐색 중 리프 노드를 찍고 돌아왔을때 어떤 위치의 a를 생각해봅시다. a는 최대 4가지의 방향으로 움직임일수 있었고 그 4가지의 움직임에 따라 4가지의 결과를 받았을 것입니다. 그 결과는 이기는 것 또는 지는것과 a와 b의 이동거리 일것입니다.

그런데 어떤 단계에서 a가 받은 결과 중 하나라도 승리했던 결과가 있다면 a는 무조건 그 점으로 갈 것입니다. 즉, 그 단계에서의 a는 승리 할 수 밖에 없는 선택을 하는 것이죠 => 전 단계로 리턴하는 값은 a가 승리 했을때의 값을 리턴할 것입니다. => a가 최선의 움직임을 취한 것입니다.

결국, 모든 단계에서 a와 b가 각 각 승리를 취하는 점을 선택한다면 => 결국 a와 b는 최선의 움직임을 취하게 되는 것입니다.

생각보다 어렸웠고 뭔가 새로운 시각을 가지게 된 것 같아서 즐겁기도 했습니다.

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

문제해설

Tags