프로그래머스 (Java) 160585 : 혼자서 하는 틱택토

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

---

풀이

주어진 게임의 결과를 보고 판단하기에는 규칙이 없기에 완전탐색으로 풀었다.

게임판의 크기는 3*3 고정이므로 모든 경우의 수를 따져도 2^9 이다.

 

주어진 문자열 배열을 2차원 char 배열로 변경하여 순서에 따른 모든 경우의 수를 확인한다.

이 때 현재 보드판이 주어진 보드판과 같다면 true를 반환, 탐색을 종료한다.

또한 끝나는 조건 (한 줄 이상이 동일한 문자로 구성)이라면 false를 반환하여 다음 경우의 수로 넘어간다.

(보드판이 같은 조건을 먼저 판단했기에 같지 않으면서 끝나는 조건일 때는 false를 반환)

---

Java 코드

import java.util.*;

class Solution {
    private char[][] result = new char[3][3];
    
    public int solution(String[] board) {
        
        char[][] state = new char[3][3];
        for (int i = 0; i < 3; i++) {
            result[i] = board[i].toCharArray();
            Arrays.fill(state[i], '.');
        }
        
        return findState(state, false) ? 1 : 0;
    }
    
    private boolean findState(char[][] board, boolean bef) {
        // compare now state with board
        boolean isSameState = true;
        out: for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                if (board[i][j] != result[i][j]) {
                    isSameState = false;
                    break out;
                }
            }
        }
        if (isSameState) {
            return true;
        }
        
        // check end condition
        for (int i = 0; i < 3; i++) {
            if ( (board[i][0] != '.' && board[i][0] == board[i][1] && board[i][1] == board[i][2])
               || (board[0][i] != '.' && board[0][i] == board[1][i] && board[1][i] == board[2][i]) ) {
                return false;
            }
        }
        if (board[1][1] != '.' && ((board[0][0] == board[1][1] && board[1][1] == board[2][2])
            || (board[0][2] == board[1][1] && board[1][1] == board[2][0])) ) {
            return false;
        }
        
        // make nextState
        char nowChar = bef ? 'X' : 'O';
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                if (board[i][j] == '.') {
                    board[i][j] = nowChar;
                    if (findState(board, !bef)) {
                        return true;
                    }
                    board[i][j] = '.';
                }
            }
        }
        return false;
    }
}