[2022 KAKAO BLIND RECRUITMENT] 사라지는 발판

최민길(Gale)·2023년 3월 29일
1

알고리즘

목록 보기
59/172

문제 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/92345

이 문제는 백트래킹을 이용하여 풀 수 있습니다. 문제의 제한 조건이 5 이하로 굉장히 작기 때문에 백트래킹을 이용한 완전탐색방식으로 풀 수 있습니다.

이 문제에서 주의해야 할 부분은 최적의 플레이를 한다는 전제입니다. 이기는 플레이어는 최대한 빨리 승리를 해야 하고, 지는 플레이어는 최대한 오래 버텨야 하기 때문에 이겼을 때의 카운트와 졌을 때의 카운트를 따로 체크하여 이동한 이후 다른 상대방의 결과가 졌을 경우 자신은 현재 시점에서 이긴 것이므로 현재 시점의 이겼을 때의 카운트 값의 최솟값으로 최신화하고, 마찬가지로 다른 상대방의 결과가 이겼을 경우 자신은 현재 시점에서 진 것이므로 현재 시점의 졌을 때의 카운트 값의 최댓값으로 최신화하는 방식으로 값을 처리해주면 됩니다.

다음은 코드입니다.

import java.util.*;

class Solution {
    static int[] dy = {1,0,-1,0};
    static int[] dx = {0,1,0,-1};
    
    static Status backtracking(int[][] board, int ay, int ax, int by, int bx, int acnt, int bcnt){
        // 초기에는 이겼는지 졌는지 알 수 없기 때문에 기본값 false로 세팅
        boolean isWin = false;
        // 자신이 이기기 위한 최악의 경우의 수는 제한 조건 값만큼 모두 이동했을 경우
        int wincnt = 5*5;
        // 자신이 지기 위한 최선의 경우의 수는 현재 상황이 지는 상황일 경우
        int losecnt = acnt+bcnt;
        
        // A가 움직일 경우
        if(acnt == bcnt && board[ay][ax]==1){
            for(int i=0;i<4;i++){
                int ny = ay + dy[i];
                int nx = ax + dx[i];
                
                if(ny<0 || ny>=board.length || nx<0 || nx>=board[0].length || board[ny][nx]==0) continue;
                
                board[ay][ax] = 0;
                
                // A가 움직였을 때 결과값 리턴
                Status s = backtracking(board,ny,nx,by,bx,acnt+1,bcnt);
                // 만약 A가 움직인 이후 결과가 모두 패배라면 가능한 모든 결과에서 A를 이길 수 없다는 뜻
                // 따라서 현재 상태는 A가 이긴 상태라고 볼 수 있음
                if(s.isWin==false) isWin = true;
                
                // 이길 수 있는 플레이어는 최대한 빨리 승리해야 한다.
                // 따라서 현재 이긴 상태라면 wincnt를 s의 cnt와의 최솟값으로 설정
                if(!s.isWin) wincnt = Math.min(wincnt,s.cnt);
                
                // 질 수 밖에 없는 플레이어는 최대한 오래 버텨야 한다.
                // 따라서 현재 진 상태라면 losecnt를 s의 cnt와의 최댓값으로 설정
                else losecnt = Math.max(losecnt,s.cnt);
                
                board[ay][ax] = 1;
            }
        }
        
        // B가 움직일 경우
        else if(acnt > bcnt && board[by][bx]==1){
            for(int i=0;i<4;i++){
                int ny = by + dy[i];
                int nx = bx + dx[i];
                
                if(ny<0 || ny>=board.length || nx<0 || nx>=board[0].length || board[ny][nx]==0) continue;
                
                board[by][bx] = 0;
                
                // B가 움직였을 때 결과값 리턴
                Status s = backtracking(board,ay,ax,ny,nx,acnt,bcnt+1);
                // 만약 B가 움직인 이후 결과가 모두 패배라면 가능한 모든 결과에서 B를 이길 수 없다는 뜻
                // 따라서 현재 상태는 B가 이긴 상태라고 볼 수 있음
                if(s.isWin==false) isWin = true;
                
                // 이길 수 있는 플레이어는 최대한 빨리 승리해야 한다.
                // 따라서 현재 이긴 상태라면 wincnt를 s의 cnt와의 최솟값으로 설정
                if(!s.isWin) wincnt = Math.min(wincnt,s.cnt);
                
                // 질 수 밖에 없는 플레이어는 최대한 오래 버텨야 한다.
                // 따라서 현재 진 상태라면 losecnt를 s의 cnt와의 최댓값으로 설정
                else losecnt = Math.max(losecnt,s.cnt);
                
                board[by][bx] = 1;
            }
        }
        
        // 위의 연산이 종료된 이후
        // 이겼으면 wincnt, 졌으면 losecnt를 리턴
        return new Status(isWin, isWin ? wincnt:losecnt);
    }
    
    public int solution(int[][] board, int[] aloc, int[] bloc) {
        Status s = backtracking(board,aloc[0],aloc[1],bloc[0],bloc[1],0,0);
        return s.cnt;
    }
}

class Status{
    boolean isWin;
    int cnt;
    
    Status(boolean isWin, int cnt){
        this.isWin = isWin;
        this.cnt = cnt;
    }
}

profile
저는 상황에 맞는 최적의 솔루션을 깊고 정확한 개념의 이해를 통한 다양한 방식으로 해결해오면서 지난 3년 동안 신규 서비스를 20만 회원 서비스로 성장시킨 Software Developer 최민길입니다.

0개의 댓글