[종만북][알고스팟] TICTACTOE(틱택토) - 동적계획법(Dynamic Programming, DP) + 게임이론(Game Theory) JAVA

https://www.algospot.com/judge/problem/read/TICTACTOE

algospot.com :: TICTACTOE

코드설명

동적계획법(Dynamic Programming, DP) + 게임이론(Game Theory) 을 활용합니다.

 

문제에서 유의할점은, 무조건 'x'가 먼저 시작하는 것이 아닌, 판의 상태에 따라 그다음 두어야할 숫자가 달라집니다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
	private static int C, N, W, H, K;
    private static int answer = 0;
    private static int[] cache = new int[(int) Math.pow(3, 9)];
    private static char[][] arr;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        C = Integer.parseInt(st.nextToken());
        while(C-- > 0){
        	arr = new char[3][3];
        	
        	for(int i=0;i<3;i++) {
        		st = new StringTokenizer(br.readLine());
        		arr[i] = st.nextToken().toCharArray();
        	}
        	Arrays.fill(cache, -2);
        	
        	int oCnt = 0;
        	int xCnt = 0;
        	for(int i=0;i<3;i++) {
        		for(int j=0;j<3;j++) {
        			if(arr[i][j] == 'o') {
        				oCnt += 1;
        			}else if(arr[i][j] == 'x'){
        				xCnt += 1;
        			}
        		}
        	}

        	int result = 0;
//        	System.out.println(isFinished(arr, 'x'));
//        	System.out.println(isFinished(arr, 'o'));
//        	
//        	System.out.println("oCnt:"+oCnt+" xCnt:"+xCnt);
        	//'o'를 두어야할 차례일 경우.
        	if(xCnt == oCnt + 1) {
        		result = canWin(arr, 'o');
            	if(result == 0) System.out.println("TIE");
            	else if(result == 1) System.out.println("o");
            	else if(result == -1) System.out.println("x");
        	}
        	//'x'를 두어야할 차례일 경우
        	else if(xCnt == oCnt) {
        		result = canWin(arr, 'x');
        		if(result == 0) System.out.println("TIE");
            	else if(result == 1) System.out.println("x");
            	else if(result == -1) System.out.println("o");
        	}
        	
        	
        }
    }
    
    
    //현재 플레이어가 이길 수 있는지 확인합니다.
    //반환값 : 1 (승리), 0 (무승부), -1(패배)
    private static int canWin(char[][] board, char turn) {
    	//이전 상대가 둬서 이미 성공한 경우, 현재 플레이어는 패배한것 이다.
    	if(isFinished(board, (char) ('o' + 'x' - turn))) return -1;
    	
    	if(cache[bijection(board)] != -2) return cache[bijection(board)];
    	
    	//모든 빈 칸에 대해 시도합니다.
    	//상방의 최선의 승패를 저장합니다.
    	int minValue = 2; 
    	for(int r = 0; r < 3; r++) {
    		for(int c =0; c < 3; c++) {
    			if(board[r][c] == '.') {
    				board[r][c] = turn;
    				minValue = Math.min(minValue, canWin(board, (char) ('o' + 'x' - turn)));
    				board[r][c] = '.';
    			}
    		}
    	}
    	
    	//만약, minValue가 2라면, '.'칸이 없어서 결과를 처리하지 못한경우
    	//minValue가 0 이라면, '.'칸이 없어서 결과를 처리하지 못한경우로 이미 비긴것으로 처리한 경우
    	//플레이할 수 없거나, 어떻게 해도 비기는 것이 최선인경우
    	if(minValue == 2 || minValue == 0) return cache[bijection(board)] = 0;
    	//다음판의 게임자가 졌다면 내가 이긴것이므로 -minValue를 반환합니다.
    	return cache[bijection(board)] = -minValue;
    }
    
    static int bijection(char[][] board) {
    	int ret = 0;
    	for(int r=0; r<3; r++) {
    		for(int c =0; c<3; c++) {
    			ret = ret * 3;
    			if(board[r][c] == 'o') ret++;
    			else if(board[r][c] =='x') ret += 2;
    		}
    	}
    	return ret;
    }
    
//    private static boolean isFinished(char[][] board, char turn) {
//        // 가로, 세로 검사
//        for (int i = 0; i < 3; i++) {
//            if (board[i][0] == turn && board[i][1] == turn && board[i][2] == turn) return true;
//            if (board[0][i] == turn && board[1][i] == turn && board[2][i] == turn) return true;
//        }
//
//        // 대각선 검사
//        if (board[0][0] == turn && board[1][1] == turn && board[2][2] == turn) return true;
//        if (board[0][2] == turn && board[1][1] == turn && board[2][0] == turn) return true;
//
//        return false;
//    }
//    
    //주어진 플레이어가 승리했는지 확인합니다.
    private static boolean isFinished(char[][] board, char turn) {
    	//가로, 세로 검사
    	for(int i=0; i<3; i++) {
    		boolean isSame = true;
    		for(int j=0; j<3; j++) {
    			if(board[i][j] != turn) {
    				isSame = false;
    				break;
    			}
    		}
    		if(isSame == true) {
    			return true;
    		}
    		
    		isSame = true;
    		for(int j=0; j<3; j++) {
    			if(board[j][i] != turn) {
    				isSame = false;
    				break;
    			}
    		}
    		if(isSame == true) {
    			return true;
    		}
    		
    	}
    	
    	//대각선 검사.
    	boolean isSame = true;
    	for(int i=0;i<3;i++) {
    		if(board[i][i] != turn) {
    			isSame = false;
    			break;
    		}
    	}
    	if(isSame == true) {
    		return true;
    	}
    	
    	//대각선 검사.
    	isSame = true;
    	for(int i=0;i<3;i++) {
    		if(board[3-i-1][i] != turn) {
    			isSame = false;
    			break;
    		}
    	}
    	if(isSame == true) {
    		return true;
    	}
    	
    	return false;
    }
}