[프로그래머스] 혼자서 하는 틱택토

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

[문제해결 전략]

1. 백트래킹을 통해 혼자서 틱택토를 진행한다.

2. 게임 종료 조건이 되거나 주어진 board판과 동일한 모양이라면 종료.

 

게임 종료 조건은 빙고게임과 같이 한 줄이 O또는 X로 채워지는 것입니다.

게임은 턴제의 게임으로 O,X가 번갈아가며 진행하기 때문에 매개변수로 turn값을 주어 현재 누구의 턴인지 확인할 수 있도록 합니다.

 

class Solution {
    
    char[][] myBoard;
    String[] _board;
    int answer = 0;
    public int solution(String[] board) {
        myBoard = new char[3][3];
        _board = board;
        for(int i=0; i<3; i++){
            for(int j=0; j<3; j++){
                myBoard[i][j] = '.';
            }
        }
        playGame(myBoard, 'O');
        return answer;
    }
    void playGame(char[][] myBoard, char turn){
    	//주어진 보드판과 동일한 모양이라면 answer 갱신 후 종료
        if(findAnswer(myBoard, _board)){
            answer = 1;
            return;
        }
        //한 줄이 채워진 종료 조건이라면 종료
        if(isFinished(myBoard)) return;
        
        //틱택토 게임 진행
        for(int i=0; i<3; i++){
            for(int j=0; j<3; j++){
                if(myBoard[i][j] == '.'){
                    myBoard[i][j] = turn;
                    playGame(myBoard, (char)('O' + 'X' - turn));
                    myBoard[i][j] = '.';
                }
            }
        }
    }
    
    public boolean findAnswer(char[][] myBoard, String[] board){
        for(int i=0; i<3; i++){
            for(int j=0; j<3; j++){
                if(myBoard[i][j] != board[i].charAt(j)) return false;
            }
        }
        return true;
    }
    public boolean isFinished(char[][] board){
        //게임 종료 조건(한 줄이 다 채워지는 경우)
        if(
            board[0][0] != '.' && board[0][0] == board[0][1] && board[0][1] == board[0][2] ||
            board[1][0] != '.' && board[1][0] == board[1][1] && board[1][1] == board[1][2] ||
            board[2][0] != '.' && board[2][0] == board[2][1] && board[2][1] == board[2][2] ||
            
            board[0][0] != '.' && board[0][0] == board[1][0] && board[1][0] == board[2][0] ||
            board[0][1] != '.' && board[0][1] == board[1][1] && board[1][1] == board[2][1] ||
            board[0][2] != '.' && board[0][2] == board[1][2] && board[1][2] == board[2][2] ||
            
            board[0][0] != '.' && board[0][0] == board[1][1] && board[1][1] == board[2][2] ||
            board[0][2] != '.' && board[0][2] == board[1][1] && board[1][1] == board[2][0]
        ) return true;
        return false;
    }
}