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

이 문제는 완전 탐색을 이용해서 풀었다.

 

격자가 3 x 3 인 틱택토를 하는 문제로, 격자의 크기가 작아 모든 경우의 수를 구한 뒤 비교하는 방식으로 풀었다.

 

한 가지 주의할 점은 play를 수행할 때 게임이 끝나는 경우에 왔다고 해서 return을 하면 모든 경우를 볼 수 없다. 따라서 continue로 다음 경우들을 체크해줘야 정답이 나온다.

import java.util.*;

class Solution {
    
    List<char[][]> snapshot = new ArrayList<>();
    char[][] board = new char[3][3];
    
    public int solution(String[] b) {
        init();
        
        if (isSame(board, b)) {
            return 1;   
        }
        
        play('O');
        
        for (final char[][] temp : snapshot) {
            if (isSame(temp, b)) {
                return 1;
            }
        }
        
        return 0;
    }
    
    void init() {
        for (int y = 0; y < 3; y++) {
            for (int x = 0; x < 3; x++) {
                board[y][x] = '.';
            }
        }
    }
    
    void play(final char present) {
        for (int y = 0; y < 3; y++) {
            for (int x = 0; x < 3; x++) {
                if (board[y][x] == '.') {
                    board[y][x] = present;
                    
                    snapshot.add(copy());
                    
                    if (isEnd()) {
                        board[y][x] = '.';
                        continue;
                    }
                    
                    char next;
                    
                    if (present == 'O') {
                        next = 'X';
                    } else {
                        next = 'O';
                    }
                    
                    play(next);
                    board[y][x] = '.';
                }
            }
        }
    }
    
    char[][] copy() {
        char[][] result = new char[3][3];
        
        for (int y = 0; y < 3; y++) {
            for (int x = 0; x < 3; x++) {
                result[y][x] = board[y][x];
            }
        }
        
        return result;
    }
    
    boolean isEnd() {
        for (int y = 0; y < 3; y++) {
            if (checkRow(y)) {
                return true;
            }
        }
        
        for (int x = 0; x < 3; x++) {
            if (checkColumn(x)) {
                return true;
            }
        }
        
        final char middle = board[1][1];
        
        if (middle != '.' && middle == board[0][0] && middle == board[2][2]) {
            return true;
        }
        
        if (middle != '.' && middle == board[0][2] && middle == board[2][0]) {
            return true;
        }
        
        return false;
    }
    
    boolean checkColumn(final int x) {
        final char first = board[0][x];
        
        if (first == '.') {
            return false;
        }
        
        for (int y = 0; y < 3; y++) {
            if (first != board[y][x]) {
                return false;
            }
        }
        
        return true;
    }
    
    boolean checkRow(final int y) {
        final char first = board[y][0];
        
        if (first == '.') {
            return false;
        }
        
        for (int x = 0; x < 3; x++) {
            if (first != board[y][x]) {
                return false;
            }
        }
        
        return true;
    }
    
    boolean isSame(final char[][] com, final String[] b) {
        for (int y = 0; y < 3; y++) {
            for (int x = 0; x < 3; x++) {
                final char c = b[y].charAt(x);
                
                if (com[y][x] != c) {
                    return false;
                }
            }
        }
        
        return true;
    }
    
}