문제 접근

처음에는 최종상태만 오목처럼 체크하는건줄 알고 구현했다가 틀렸다. 문제를 다시 읽어보니,최종상태까지 도달할 수 있는지 등 여부를 모두 파악해야 하는 문제였고, 문제에서 놓을 수 있는 X돌은 최대 5개, O돌은 최대 4개로. 결국은 브루트포스로 모든 경우를 파악하면서 가지치기로 걸러내야했다.

=> 이 문제의 핵심은, 해당 상태까지 도달할 수 있는 경로(케이스)가 있느냐를 묻는 것임.

내가 한 방법은 다음과 같다.

• 아직 돌을 다 놓지 않았는데, 직전에 놓았던 돌로 인해 게임이 이미 끝났다? 그러면 그 이후는 더이상 파악 안해도 됨.
• 현재까지 놓은 돌의 갯수를 토대로, 이번에 놓을 돌의 위치가 X인지 O인지를 파악하고, 아직 놓지 않은 돌 중 하나를 배치함.
• 만약 돌을 주어진 대로 모두 배치했는데, 바둑판을 꽉채웠거나(9개), 마지막 돌로 인해 게임이 종료된거라면 result=true를 통해 게임이 성공적으로 종료될 수 있는 케이스가 있다는 것을 기록하면 된다.

문제 풀이

import java.io.*;
import java.util.*;

class Main {
    static ArrayList<Point> xPoints = new ArrayList<>();
    static ArrayList<Point> oPoints = new ArrayList<>();
    static boolean[] xUse = new boolean[3];
    static boolean[] oUse = new boolean[3];
    static char[][] checkBoard;
    static boolean result = false;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        String invalid = "invalid";
        String valid = "valid";
        while (true) {
            String input = br.readLine();
            if (input.equals("end")) break;
            char[][] board = new char[3][3];
            xPoints = new ArrayList<>();
            oPoints = new ArrayList<>();
            for (int i = 0; i < 9; i += 3) {
                for (int j = i; j < i + 3; j++) {
                    char curChar = input.charAt(j);
                    board[i / 3][j - i] = curChar;
                    if (curChar == 'X') {
                        xPoints.add(new Point(i / 3, j - i));
                    }
                    if (curChar == 'O') {
                        oPoints.add(new Point(i / 3, j - i));
                    }
                }
            }
            int xCount = xPoints.size();
            int oCount = oPoints.size();

            if (xCount == oCount || xCount == oCount + 1) {
                xUse = new boolean[xCount];
                oUse = new boolean[oCount];
                checkBoard = new char[3][3];
                result = false;
                dfs(0, xCount + oCount);
                if (result) {
                    sb.append(valid).append("\n");
                } else {
                    sb.append(invalid).append("\n");
                }
            } else {
                sb.append(invalid).append("\n");
            }
        }

        System.out.println(sb);
    }

    static void dfs(int curCount, int endCount) {
        char curUser = (curCount % 2 == 0) ? 'X' : 'O';
        char nextUser = (curUser == 'X') ? 'O' : 'X';

        if (curCount == endCount) {
            if (endCount == 9 || isFinish(checkBoard, nextUser)) {
                result = true;
            }
            return;
        } else if (isFinish(checkBoard, nextUser)) return;

        ArrayList<Point> curPoints = (curUser == 'X') ? xPoints : oPoints;
        boolean[] curUse = (curUser == 'X') ? xUse : oUse;

        for (int i = 0; i < curPoints.size(); i++) {
            if (curUse[i]) continue;
            Point point = curPoints.get(i);

            curUse[i] = true;
            checkBoard[point.x][point.y] = curUser;
            dfs(curCount + 1, endCount);
            checkBoard[point.x][point.y] = '.';
            curUse[i] = false;
        }
    }

    static boolean isFinish(char[][] board, char findChar) {
        // 행검사
        for (int i = 0; i < 3; i++) {
            boolean subIsFind = true;
            for (int j = 0; j < 3; j++) {
                if (board[i][j] != findChar) {
                    subIsFind = false;
                }
            }
            if (subIsFind) return true;
        }

        // 열검사
        for (int j = 0; j < 3; j++) {
            boolean subIsFind = true;
            for (int i = 0; i < 3; i++) {
                if (board[i][j] != findChar) {
                    subIsFind = false;
                }
            }
            if (subIsFind) return true;
        }

        boolean subIsFind = true;
        for (int i = 0; i < 3; i++) {
            if (board[i][i] != findChar) {
                subIsFind = false;
            }
        }
        if (subIsFind) return true;

        subIsFind = true;
        for (int i = 0; i < 3; i++) {
            if (board[i][2 - i] != findChar) {
                subIsFind = false;
            }
        }
        if (subIsFind) return true;

        return false;
    }

    static class Point {
        final int x;
        final int y;

        Point(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
}