[Python] 사라지는 발판

1. 문제

https://programmers.co.kr/learn/courses/30/lessons/92345

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

 

2. 풀이

• MinMax Algorithm 사용

MinMax Algorithm

두명이 돌아가면서 작업을 하는 과정에서, 각자 자신이 이길 수 있는 최선의 선택을 할 때 필요한 알고리즘

내가 푼 방법

*단어 정리* state : 현재 상태 now_player : 현재 움직이는 사람 step : 몇 스텝만에 이겼는지

1. 현재 플레이어를 상하좌우로 움직인 뒤, 현재 플레이어와 상대 플레이어의 parameter의 순서를 바꿔서 play함수를 부름

다음 턴에서는 상대방 플레이어가 주 플레이어가 됨 play(주플레이어x, 주플레이어y, 상대플레이어x, 상대플레이어y ) <- 이런식으로 부르는데 주 플레이어와 상대 플레이어가 회차별로 바뀌므로 parameter 순서를 바꿔주어야 함!

1. 만약 더이상 갈 곳이 없다면 = 상하좌우로 for문을 돌렸는데 play함수를 부르지 못했다면 or 내가 있던 자리가 사라졌다면

내가 진 상태로 return

1. 리턴 될 때, 이긴 사람이 누구인지를 함께 리턴함

A가 이긴 사람이면 : True B가 이긴 사람이면 : False

1. for문안에서 play 함수가 불렸고, play함수에서 리턴된 값이 돌아왔다면?

1) 현재 내가 지고 있는데, 리턴된 값은 내가 이기는 방법이면 - 현재 내가 이기는 방법으로 update 2) 현재 내가 지고 있는데, 리턴된 값도 내가 지는 방법이면 - 더 오래 버티는 방법 : Max 값으로 update 3) 현재 내가 이기고 있는데, 리턴된 값도 내가 이기는 방법이면 - 더 빨리 이기는 방법 : Min 값으로 update 4) 현재 내가 이기고 있는데, 리턴된 값은 내가 지는 방법이라면 - 무시

회고

• Minmax Algorithm이라는 이름이 있기는 하지만, 결국은 완전 탐색을 베이스로 한 알고리즘 이기 때문에, 굳이 저 용어를 모르더라도 충분히 풀 수 있었던 문제였던 것 같다.
• 쫄지말고 천천히 다 탐색하는 게 중요했었는듯!

 

3. 코드

#양옆위아래 움직이기
dx = [1,-1,0,0]
dy = [0,0,1,-1]

# A가 true
# B가 false

def play(nowx, nowy, otherx, othery, now_player):
    
    # 지금 있는곳이 사라지면 = 현재 플레이어는 짐
    if visit[nowx][nowy] == 0:
        return (not now_player), 0
    
    # 일단 지는거로 냅둠 (좌우 양옆 이동했는데도 지고 있으면 진거)
    state = False
    step = 0

    for i in range(4):
        # 다음으로 갈곳
        nx = nowx + dx[i]
        ny = nowy + dy[i]
        
        # 보드 밖으로 가면 멈춤
        if nx >= w or ny >= h or nx < 0 or ny < 0 : 
            continue
        # 이미 갔던 곳이면 멈춤
        if visit[nx][ny] == 0 :
            continue

        visit[nowx][nowy] = 0
        # 상대랑 나랑 턴이 바뀜 -> 게임 다시 진행
        if now_player:
            pre_winner, pre_step = play(otherx, othery, nx, ny, False)
        else:
            pre_winner, pre_step = play(otherx, othery, nx, ny, True)
        
        # 칸수 + 1 
        pre_step = pre_step + 1
        
        # 백트래킹
        visit[nowx][nowy] = 1
        
        # 지금 차례인 사람이 지고 있는데 (=state)
        # 이 전 상태가 이기는 방법일 경우 :
        if not state and (pre_winner == now_player):
            step = pre_step
            state = True
        # 이 전 상태도 지는 방법일 경우 -> 오래 버티는 방법
        elif not state and (pre_winner != now_player): 
            step = max(pre_step, step)
        # 지금 차례인 사람이 이기고 있으면, 이전도 이길때만 업뎃 & 걍 빨리 이기기! 
        elif state and (pre_winner == now_player): 
            step = min(pre_step, step)
    
    if now_player == state:
        winner = True
    else:
        winner = False
    return winner, step


def solution(board_list, aloc, bloc):
    
    global w,h,visit
    w, h = len(board_list), len(board_list[0])
    # 방문 여부 체크용
    visit = board_list
    winner, answer = play(aloc[0], aloc[1], bloc[0], bloc[1],True)
    return answer

# solution([[1, 1, 1], [1, 1, 1], [1, 1, 1]],	[1, 0],	[1, 2])