백준 7682번 <틱택토>

백준 알고리즘 7682번

https://www.acmicpc.net/problem/7682

7682번: 틱택토

---

7682번

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

 

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

 

출력으로 각 테스트케이스마다 정답을 출력한다. 가능할 경우 valid를 불가능할 경우 invalid를 출력하면 된다.

---

문제 해결

게임이 끝나는 경우를 확인하면 된다.

• 게임이 순서대로 잘 진행되었는지를 확인했다.
  • X가 먼저 시작하기 때문에 X의 개수가 1개 더 많거나 X와 O의 개수가 같아야 한다.
• 빙고가 만들어졌으면 게임이 끝난다. 
  • X도 빙고를 만들었고 O도 빙고를 만드는 경우는 존재할 수 없다. X가 먼저 빙고를 만들었기 때문에 O로 빙고가 만들어지기 전에 끝났어야 한다.
  • X의 최대 개수는 5개이고 O의 최대 개수는 4개이다. X는 빙고를 최대 2개 만들 수 있고 O는 1개만 만들 수 있다.
    • X가 빙고를 1개 이상 만들었고 X의 개수가 1개 더 많다면 게임이 끝난다.
    • O가 빙고를 1개 만들었고 X의 개수와 O의 개수가 같다면 게임이 끝난다.
• 빙고가 만들어지지 않았고 더 이상 놓을 곳이 없다면 게임이 끝난다.

---

코드

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

public class Main {
    static char[][] Board;
    static StringBuilder sb;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        sb = new StringBuilder();
        boolean chk = false;
        while (true) {
            String input = br.readLine();
            if (input.equals("end")) break;
            chk = true;
            if (process(input)) sb.append("valid").append("\n");
            else sb.append("invalid").append("\n");
        }
        if (chk)
            System.out.println(sb.toString());
    }

    static boolean process(String str) {
        Board = new char[3][3];
        int cntO = 0;
        int cntX = 0;
        for (int i = 0; i < str.length(); i++) {
            if (str.charAt(i) == 'O') cntO++;
            if (str.charAt(i) == 'X') cntX++;
            int a = i / 3;
            int b = i % 3;
            Board[a][b] = str.charAt(i);
        }
        if (cntO+cntX == 0) return true;
        if (!(cntO==cntX || cntX == (cntO+1))) {
            return false;
        }
        int[] chk = checkBoard();
        // X랑 O랑 둘 다 빙고면 false
        if (chk[0] > 0 && chk[1] > 0) return false;

        if (chk[0] >= 1) return cntX == (cntO+1);
        if (chk[1] == 1) return  cntX == cntO;

        // 더이상 놓을 곳이 없으면 true
        return (cntX + cntO)== 9;
    }
    // 빙고를 만들었는지
    static int[] checkBoard(){
        int[] arr = new int[2];     // {'X', 'O'}
        for (int i = 0; i < 3; i++) {
            char chI = Board[i][0];
            char chJ = Board[0][i];
            int I = 1;  // 행 확인
            int J = 1;  // 열 확인
            for (int j = 1; j < 3; j++) {
                if (chI != '.' && chI == Board[i][j]) {
                    I++;
                }
                if (chJ != '.' && chJ == Board[j][i]){
                    J++;
                }
            }
            if (I == 3) {
                if (chI == 'X') arr[0]++;
                if (chI == 'O') arr[1]++;
            }
            if (J == 3) {
                if (chJ == 'X') arr[0]++;
                if (chJ == 'O') arr[1]++;
            }
        }
        // 대각선 확인
        if ('.' != Board[0][2] && Board[0][2] == Board[1][1] && Board[1][1] == Board[2][0]){
            if (Board[1][1] == 'X') arr[0]++;
            if (Board[1][1] == 'O') arr[1]++;
        }
        if ('.' != Board[0][0] && Board[0][0] == Board[1][1] && Board[1][1] == Board[2][2]){
            if (Board[1][1] == 'X') arr[0]++;
            if (Board[1][1] == 'O') arr[1]++;
        }
        return arr;
    }

}

---

결과

 

---

XOXXOXXOO
X..XOOX.O
XOX.OXXOO
XXXOOOXXX
OXOOOOOXO
end

invalid
invalid
valid
invalid
invalid

.........
...XOOXOX
.XO..X.OX
XXOOXXOOX
XXOOXXXOO
end

valid
invalid
invalid
valid
valid

XOXOXOXO.
XOXOXOX..
XOXOXOXOX
XOXOXXOOX
end

invalid
valid
valid
valid