[PCCP] Lv3: 사라지는 발판(92345) 해설

문제

- 문제 링크: 사라지는 발판

 

해설

- 자료구조: 

- 시간복잡도: 

 

(풀이과정)

1) 

2) 

3) 

4) 

 

코드

(C언어)

solution 1)

solution 1

#include<>

solution 2)

#include<>

solution 3)

#include<>

 

(C++)

solution 1)

#include<>

solution 2)

#include<>

solution 3)

#include<>

 

(C#)

solution 1)

#include<>

solution 2)

#include<>

solution 3)

#include<>

 

(Java)

solution 1) 

- N: board의 가로 길이

- M: board의 세로 길이

- 각 위치에서 상하좌우 4개의 경우의 수 존재

- 최종 시간 복잡도: O(4^(M*N))

import java.util.ArrayList;
import java.util.Comparator;

class Solution {
    // 백트래킹을 위한 재귀 메서드의 반환값을 저장
    private static class Result {
        boolean win;
        int step;
        
        public Result(boolean win, int step) {
            this.win = win;
            this.step = step;
        }
    }
    
    // 게임판의 행과 열의 개수를 저장
    private static int ROW, COL;
    
    // 이동할 수 있는 방향을 저장. 좌, 하, 우, 상 순서로 저장
    private static final int[] DR = {0, 1, 0, -1};
    private static final int[] DC = {-1, 0, 1, 0};
    private static boolean[][] visited;
    private static int[][] Board;
    
    // 주어진 위치가 유효한 위치인지 확인하는 메서드
    private static boolean isValidPos(int r, int c) {
        return 0 <= r && r < ROW && 0 <= c && c < COL;
    }
    
    // 재귀적으로 호출되는 메서드
    private static Result recursive(int[] alpha, int[] beta, int step) {
        // 현재 플레이어의 위치와 이동 가능한지 여부, 상대 플레이어가 이긴 경우를 저장하는 변수들
        int[] now = step % 2 == 0 ? alpha : beta;
        boolean canMove = false;
        boolean isOpponentWinner = true;
        
        // 이긴 경우와 지는 경우를 저장하는 리스트
        ArrayList<Integer> winSteps = new ArrayList<>();
        ArrayList<Integer> loseSteps = new ArrayList<>();
        
        // 현재 위치에서 이동할 수 있는 모든 방향으로 이동
        for (int i = 0; i <4; ++i) {
            int nr = now[0] + DR[i];
            int nc = now[1] + DC[i];
            // 이동할 수 있는 위치인 경우
            if (isValidPos(nr, nc) && !visited[nr][nc] && Board[nr][nc] == 1) {
                canMove = true;
                // 두 플레이어의 위치가 같으면 A 플레이어가 이긴 것이므로 true와 step + 1을 반환
                if (alpha[0] == beta[0] && alpha[1] == beta[1])
                    return new Result(true, step + 1);
                    
                // 재귀적으로 호출하여 이긴 여부와 남은 턴 수를 가져옴
                visited[now[0]][now[1]] = true;
                Result result = step % 2 == 0 ? recursive(new int[]{nr, nc}, beta, step + 1)
                    : recursive(alpha, new int[]{nr, nc}, step + 1);
                visited[now[0]][now[1]] = false;
                
                // 상대 플레이어가 이긴 경우만 true로 유지
                isOpponentWinner &= result.win;
                // 이긴 경우와 지는 경우를 저장
                if (result.win)
                    winSteps.add(result.step);
                else
                    loseSteps.add(result.step);
            }
        }
        
        // 이동할 수 있는 위치가 없는 경우
        if (!canMove)
            return new Result(false, step);
        // 상대 플레이어가 이긴 경우
        if (isOpponentWinner)
            return new Result(false, winSteps.stream().max(Comparator.comparingInt(o -> o)).get());
        // 현재 플레이어가 이긴 경우
        return new Result(true, loseSteps.stream().min(Comparator.comparingInt(o -> o)).get());
    }
    
    public static int solution(int[][] board, int[] aloc, int[] bloc) {
        Board = board;
        ROW = board.length;
        COL = board[0].length;
        visited = new boolean[ROW][COL];
        // A 플레이어가 이길 때까지 걸리는 최소 턴 수를 반환
        return recursive(aloc, bloc, 0).step;
    }
}

solution 2)

#include<>

solution 3)

#include<>

 

(Python)

solution 1)

- N: board의 가로 길이

- M: board의 세로 길이

- 각 위치에서 상하좌우 4개의 경우가 있으므로 최종 시간 복잡도: O(4^(M*N))

def solution(board, aloc, bloc):
    # 게임판의 행과 열의 개수를 저장
    ROW, COL = len(board), len(board[0])
    # 이동할 수 있는 방향을 저장. 상, 우, 하, 좌 순서로 저장
    DR, DC = [-1, 0, 1, 0], [0, 1, 0, -1]
    
    # 주어진 위치가 유효한 위치인지 확인하는 함수
    def is_valid_pos(r, c):
        return 0 <= r < ROW and 0 <= c < COL
        
    # 재귀적으로 호출되는 함수
    def recursive_func(alpha_pos, beta_pos, visited, step):
        # 현재 플레이어의 위치와 이동 가능한지 여부, 상대 플레이어가 이긴 경우를 저장하는 변수들
        r, c = alpha_pos if step % 2 == 0 else beta_pos
        can_move = False
        is_opponent_winner = True
        # 이긴 경우와 지는 경우를 저장하는 리스트
        win_steps, lose_steps = [], []
        
        # 현재 위치에서 이동할 수 있는 모든 방향으로 이동
        for i in range(4): 
            nr, nc = r + DR[i], c + DC[i]
            # 이동할 수 있는 위치인 경우
            if is_valid_pos(nr, nc) and (nr, nc) not in visited and board[nr][nc]:
                can_move = True
                # 두 플레이어의 위치가 같으면 A 플레이어가 이긴 것이므로 True와 step+1을 반환
                if alpha_pos == beta_pos:
                    return True, step + 1
                
                # 재귀적으로 호출하여 이긴 여부와 남은 턴 수를 가져옴
                win, steps_left = (
                    recursive_func([nr, nc], beta_pos, visited | {(r, c)}, step + 1)
                    if step % 2 == 0
                    else recursive_func(
                        alpha_pos, [nr, nc], visited | {(r, c)}, step + 1
                    )
                )
                
                # 상대 플레이어가 이긴 경우만 True 유지
                is_opponent_winner &= win
                # 이긴 경우와 지는 경우를 저장
                (win_steps if win else lose_steps).append(steps_left)
                
        # 이동할 수 있는 위치가 없는 경우
        if not can_move:
            return False, step
        # 상대 플레이어가 이긴 경우
        if is_opponent_winner:
            return False, max(win_steps)
        # 현재 플레이이가 이긴 경우
        return True, min(lose_steps)
        
    # A 플레이어가 이길 때까지 걸리는 최소 턴 수를 반환
    _, steps = recursive_func(aloc, bloc, set(), 0)
    return steps

solution 2)

import

solution 3)

import

 

(JavaScript)

solution 1)

- N: board의 가로 길이

- M: board의 세로 길이

- 각 위치에 상하좌우 4개의 경우가 존재하므로 최종 시간 복잡도: O(4^(M*N))

function solution(board, aloc, bloc) {
    // 게임판의 행과 열의 개수를 저장
    const ROW = board.length;
    const COL = board[0].length;
    
    // 이동할 수 있는 방향을 저장합니다. 상, 우, 하, 좌 순서로 저장
    const DR = [-1, 0, 1, 0];
    const DC = [0, 1, 0, -1];
    
    // 주어진 위치가 유효한 위치인지 확인하는 함수
    function isValidPos(r, c) {
        return 0 <= r && r < ROW && 0 <= c && c < COL;
    }
    
    // 재귀적으로 호출되는 함수
    function recursiveFunc(alphaPos, betaPos, visited, step) {
        // 현재 플레이어의 위치와 이동 가능한지 여부, 상대 플레이어가 이긴 경우를 저장하는 변수들
        const [r, c] = step % 2 === 0 ? alphaPos : betaPos;
        let canMove = false;
        let isOpponentWinner = true;
        
        // 이긴 경우와 지는 경우를 저장하는 배열
        const winSteps = [];
        const loseSteps = [];
        
        // 현재 위치에서 이동할 수 있는 모든 방향으로 이동
        for (let i = 0; i < 4; ++i) {
            const nr = r + DR[i];
            const nc = c + DC[i];
            
            // 이동할 수 있는 위치인 경우
            if (isValidPos(nr, nc) && !visited.has(`${nr},${nc}`) && board[nr][nc]) {
                canMove = true;
                // 두 플레이어의 위치가 같으면 A 플레이어가 이긴 것이므로 true와 step + 1을 반환
                if (alphaPos[0] === betaPos[0] && alphaPos[1] === betaPos[1]) {
                    return [true, step + 1];
                }
                
                // 재귀적으로 호출하여 이긴 여부와 나은 턴 수를 가져옴
                const [win, stepsLeft] = step % 2 === 0
                    ? recursiveFunc([nr, nc], betaPos, new Set([...visited, `${r},${c}`]), step + 1)
                    : recursiveFunc(alphaPos, [nr, nc], new Set([...visited, `${r},${c}`]), step + 1);
                    
                // 상대 플레이어가 이긴 경우만 true로 유지
                isOpponentWinner &= win;
                
                // 이긴 경우와 지는 경우를 저장
                if (win) {
                    winSteps.push(stepsLeft);
                } else {
                    loseSteps.push(stepsLeft);
                }
            }
        }
        
        // 이동할 수 있는 위치가 없는 경우
        if (!canMove) {
            return [false, step];
        }
        
        // 상대 플레이어가 이긴 경우
        if (isOpponentWinner) {
            return [false, Math.max(...winSteps)];
        }
        
        // 현재 플레이어가 이긴 경우
        return [true, Math.min(...loseSteps)];
    }
    
    // A 플레이어가 이길 때까지 걸리는 최소 턴 수를 반환
    const [_, steps] = recursiveFunc(aloc, bloc, new Set(), 0);
    
    return steps;
}

solution 2)

import

solution 3)

import