[Algo] 백준 7682 틱택토 JAVA

문제 바로가기 : https://www.acmicpc.net/problem/7682

메모리 : 14116KB

시간 : 120ms

언어 : Java 11

---

코드

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

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

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        // 최종상태가 되는 방법
        // 게임판이 가득 찼다: X=5개 O=4개
        // 3목이 되었다 반례: 3목이 2개는 불가능하다 또 반례: X의 경우 연결된 3목2개는 가능하다
        while (true) {
            String str = br.readLine();
            if (str.equals("end")) {
                break;
            }
            tic = new char[3][3];
            for (int i = 0; i < 9; i++) {
                tic[i / 3][i % 3] = str.charAt(i);
            }
            // 삼목이 되는지 확인
            // 0=안됨 1=됨 2=삼목이성립했으나 조건에 맞지않음
            int flag = isThree();

            // 삼목이 안되면 가득차있는지 확인
            if (flag == 0) {
                flag = isFull();
            }

            if (flag == 1) {
                sb.append("valid").append("\n");
            } else {
                sb.append("invalid").append("\n");
            }
        }
        System.out.print(sb);
    }

    private static int isFull() {
        int cntX = 0;
        int cntO = 0;
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                if (tic[i][j] == 'X') {
                    cntX++;
                } else if (tic[i][j] == 'O') {
                    cntO++;
                }
            }
        }
        if (cntX == 5 && cntO == 4) {
            return 1;
        }
        return 0;
    }

    private static int isThree() {
        int cntX = 0;
        int cntO = 0;
        // 가로세로
        for (int i = 0; i < 3; i++) {
            if (tic[i][0] == tic[i][1] && tic[i][0] == tic[i][2]) {
                if (tic[i][0] == 'O') {
                    cntO++;
                } else if (tic[i][0] == 'X') {
                    cntX++;
                }
            }
            if (tic[0][i] == tic[1][i] && tic[0][i] == tic[2][i]) {
                if (tic[0][i] == 'O') {
                    cntO++;
                } else if (tic[0][i] == 'X') {
                    cntX++;
                }
            }
        }
        // 대각선
        if (tic[0][0] == tic[1][1] && tic[0][0] == tic[2][2]) {
            if (tic[1][1] == 'O') {
                cntO++;
            } else if (tic[1][1] == 'X') {
                cntX++;
            }
        }
        if (tic[0][2] == tic[1][1] && tic[1][1] == tic[2][0]) {
            if (tic[1][1] == 'O') {
                cntO++;
            } else if (tic[1][1] == 'X') {
                cntX++;
            }
        }
        // 삼목성립
        // X가 1개 이상인 경우 가능
        if (cntX > 0 && cntO == 0) {
            int X = 0;
            int O = 0;
            for (int i = 0; i < 3; i++) {
                for (int j = 0; j < 3; j++) {
                    if (tic[i][j] == 'X') {
                        X++;
                    } else if (tic[i][j] == 'O') {
                        O++;
                    }
                }
            }
            // 개수가 맞아야 한다. X가 이기는경우 X가 하나 더 많음
            if (X - O == 1) {
                return 1;
            }
            return 2;
        }
        // O가 삼목이면서 X가 없는경우 가능
        else if (cntO == 1 && cntX == 0) {
            int X = 0;
            int O = 0;
            for (int i = 0; i < 3; i++) {
                for (int j = 0; j < 3; j++) {
                    if (tic[i][j] == 'X') {
                        X++;
                    } else if (tic[i][j] == 'O') {
                        O++;
                    }
                }
            }
            // O가 이기는 경우 판이 다 차면안되고, 개수가 같아야 한다.
            if (X < 5 && X == O) {
                return 1;
            }
            return 2;
        } else if (cntO == 1 && cntX == 1) {
            return 2;
        }
        return 0;
    }
}

풀이

반례가 엄청 많은 구현문제

최종상태가 되는 방법

• 게임판이 가득 찼다: X=5개 O=4개
• 3목이 되었다 반례: 3목이 2개는 불가능하다 또 반례: X의 경우 연결된 3목2개는 가능하다

이것을 바탕으로 반례를 하나씩 걸러가며 체크해줬다.

10프로에서 틀렸었었는데, 삼목이 성립하고 판이 가득 찼지만 정답이 안되는 경우 = O가 3목, X가 3목인 경우 를 거르지 못했기 때문이었다. 삼목인경우에서 false인 경우 isfull에서 true가 나와서 정답처리가 되는 것이다. 이를 방지하기 위해 삼목의 return을 3가지 경우로 만들고, 상기한 경우를 2번으로 놓아 삼목이 성립되면서 정답이 아닌 경우를 따로 처리했다.