[프로그래머스] 사라지는 발판 (Python, 2022 카카오 blind recruitment)

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

프로그래머스

 

 

☁️ 문제 설명

• 게임이 끝날 때까지 양 플레이어가 캐릭터를 몇 번 움직이게 될지 예측하기
• 게임 규칙
  • 플레이어 A, B가 게임을 함
  • 자신의 캐릭터 하나를 보드에 올려놓고 시작
  • 게임 보드는 발판 있는 부분과 없는 부분이 존재
  • 발판 있는 부분에만 캐릭터가 설 수 있음
  • 캐릭터는 발판이 있는 곳으로만 이동 가능
  • 보드 밖으로는 이동 불가능
  • 밟고 있던 발판은 캐릭터가 움직이는 동시에 사라짐 (1->0)
  • 상하좌우 인접한 4개의 칸 중 발판이 있는 칸으로 옮기기 (bfs, dfs)
  • 패자 승자 정해지는 룰
    • 1. 움질일 차례인데 상하좌우에 모두 발판이 없을 경우 or 보드 밖이라 이동 불가할 경우
    • 2. 두 캐릭터가 같은 발판 위에 있을 때 상대 플레이어의 캐릭터가 다른 발판으로 이동해 자신의 캐릭터가 서있던 발판이 사라질 경우
  • 항상 A 먼저 시작
  • 항상 이기는 플레이어는 빨리 승리하도록, 항상 지는 플레이어는 최대한 오래 버티도록

 

☁️ 입출력

• 입력
  • `board`: 게임 보드의 초기 상태인 2차원 정수 배열
    • [[1,1,1],[1,1,1],[1,1,1]]
  • `aloc`: 플레이어 A의 초기 위치인 정수 배열
    • [1,0]
  • `bloc`: 플레이어 B의 초기 위치인 정수 배열
• 출력
  • 두 캐릭터가 움직인 횟수

 

---

💡 풀이 아이디어

• 항상 이기는 플레이어와 항상 지는 플레이어를 어떻게 판단할지? -> `DFS`
• 재귀 함수로 모든 경우를 시도해보고
  • 상대가 지는 경우가 하나라도 있으면, 나는 이김 -> 최소 횟수로 이기기
  • 모든 경우에서 상대가 이기면, 나는 짐 -> 최대 횟수로 지기
• DFS + 구현

 

🚨 주의할 점

• BFS로는 풀 수 없음 
  • 승패는 모든 경우의 결과에 의존되기 때문

 

---

💻 코드

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

def dfs(ax, ay, bx, by, flag, board):
    # flag == True면 A 차례, False면 B차례
    if flag:
        x, y = ax, ay
    else:
        x, y = bx, by
    
    # 현재 위치에 발판이 없으면
    if board[x][y] == 0:
        return (False, 0)
    
    can_win = False
    min_turn = 10**9
    max_turn = 0
    
    moved = False
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        
        if 0 <= nx < len(board) and 0 <= ny < len(board[0]) and board[nx][ny] == 1:
            moved = True
            board[x][y] = 0
            
            # flag == True면 A 차례, False면 B차례
            if flag: 
                win, turns = dfs(nx, ny, bx, by, False, board)
            else:
                win, turns = dfs(ax, ay, nx, ny, True, board)
            
            board[x][y] = 1
            
            # 상대가 지는 경우가 하나라도 있으면 A는 승리, 모든 경우가 상대 승리면 A는 최대한 늦게 져야함
            if not win:
                can_win = True
                min_turn = min(min_turn, turns + 1)
            else: 
                max_turn = max(max_turn, turns + 1)
    
    # 주위에 발판이 없으면 패배
    if not moved:
        return (False, 0)
    
    # 이기는 경우가 있으면 최소한의 움직임, 지는 경우라면 최대한 늦게 지기
    if can_win:
        return (True, min_turn)
    else:
        return (False, max_turn)

def solution(board, aloc, bloc):
    win, turns = dfs(aloc[0], aloc[1], bloc[0], bloc[1], True, board)
    return turns