[백준]#7682 틱택토

문제

틱택토 게임은 두 명의 사람이 번갈아가며 말을 놓는 게임이다. 게임판은 3×3 격자판이며, 처음에는 비어 있다. 두 사람은 각각 X 또는 O 말을 번갈아가며 놓는데, 반드시 첫 번째 사람이 X를 놓고 두 번째 사람이 O를 놓는다. 어느 때든지 한 사람의 말이 가로, 세로, 대각선 방향으로 3칸을 잇는 데 성공하면 게임은 즉시 끝난다. 게임판이 가득 차도 게임은 끝난다.

게임판의 상태가 주어지면, 그 상태가 틱택토 게임에서 발생할 수 있는 최종 상태인지를 판별하시오.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 줄은 9개의 문자를 포함하며, 'X', 'O', '.' 중 하나이다. '.'은 빈칸을 의미하며, 9개의 문자는 게임판에서 제일 윗 줄 왼쪽부터의 순서이다. 입력의 마지막에는 문자열 "end"가 주어진다.

출력

각 테스트 케이스마다 한 줄에 정답을 출력한다. 가능할 경우 "valid", 불가능할 경우 "invalid"를 출력한다.

예제 입력

XXXOO.XXX
XOXOXOXOX
OXOXOXOXO
XXOOOXXOX
XO.OX...X
.XXX.XOOO
X.OO..X..
OOXXXOOXO
end

예제 출력

invalid
valid
invalid
valid
valid
invalid
invalid
invalid

풀이

이 문제는 BFS, DFS 알고리즘을 이용하면 풀 수 있다고 한다. 하지만 모든 경우의 수를 생각해서 조건문으로 풀 수 있다.

import java.io.InputStreamReader;
import java.io.BufferedReader;
import java.io.IOException;

public class Main {
    static char[][] map;

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        while(true) {
            String input = br.readLine();
            if(input.equals("end"))
                break;

            int one = 0;
            int two = 0;
            int empty = 0;
            map = new char[3][3];
            for(int i=0; i<9; i++) {
                map[i/3][i%3] = input.charAt(i);
                if(map[i/3][i%3]=='X') one++;

                else if(map[i/3][i%3]=='O') two++;

                else empty++;
            }

            if(two>one || two>=one&&empty==0 || Math.abs(one-two)>1 || one==0&&two==0) {
                System.out.println("invalid");
                continue;
            }

            else
                sol(empty, one-two);
        }
    }

    public static void sol(int empty, int minus) {
        int xBingo = 0;
        int oBingo = 0;
        int center = 0;
        int[] db = new int[4];

        if(map[0][0] == map[0][1] && map[0][1] == map[0][2]) {
            if(map[0][0]=='X') {
                xBingo++;
                db[0]++;
            }

            else if(map[0][0]=='O') oBingo++;
        }

        if(map[1][0] == map[1][1] && map[1][1] == map[1][2]) {
            if(map[1][0]=='X') {
                xBingo++;
                center++;
            }

            else if(map[1][0]=='O') oBingo++;
        }

        if(map[2][0] == map[2][1] && map[2][1] == map[2][2]) {
            if(map[2][0]=='X') {
                xBingo++;
                db[1]++;
            }

            else if(map[2][0]=='O') oBingo++;
        }

        if(map[0][0] == map[1][0] && map[1][0] == map[2][0]) {
            if(map[0][0]=='X') {
                xBingo++;
                db[2]++;
            }

            else if(map[0][0]=='O') oBingo++;
        }

        if(map[0][1] == map[1][1] && map[1][1] == map[2][1]) {
            if(map[0][1]=='X') {
                xBingo++;
                center++;
            }

            else if(map[0][1]=='O') oBingo++;
        }

        if(map[0][2] == map[1][2] && map[1][2] == map[2][2]) {
            if(map[0][2]=='X') {
                xBingo++;
                db[3]++;
            }

            else if(map[0][2]=='O') oBingo++;
        }

        if(map[0][0] == map[1][1] && map[1][1] == map[2][2]) {
            if(map[0][0]=='X') {
                xBingo++;
                center++;
            }

            else if(map[0][0]=='O') oBingo++;
        }

        if(map[0][2] == map[1][1] && map[1][1] == map[2][0]) {
            if(map[0][2]=='X') xBingo++;

            else if(map[0][2]=='O') oBingo++;

            center++;
        }

        if(xBingo==1 && oBingo==0 && minus==1 || xBingo==0 && oBingo==1 && minus==0 || xBingo==0 && oBingo==0 && empty==0 && minus==1 || xBingo==2 && oBingo==0 && center>=1 && empty==0 || xBingo==2&&oBingo==0&&empty==0&&(db[0]==1&&db[2]==1||db[0]==1&&db[3]==1||db[1]==1&&db[2]==1||db[1]==1&&db[3]==1))
            System.out.println("valid");
        else
            System.out.println("invalid");
    }
}