백준 7682번: 틱택토

문제 설명

• 주어진 입력이 틱택토 최종결과로 가능한 경우인지를 판별하는 문제입니다.

접근법

• 조건문을 통해 경우의 수를 가지치기 해야 합니다.
• 두줄 동시에 완성되는 경우(XOXOXOXOX)는 얼핏보면 특별한 경우의 수로 보입니다.
  • 두 줄이 동시에 완성되려면 5개의 O or X가 필요합니다.
    • O는 5개가 존재할 수 없기 때문에 O로 두 줄을 동시에 완성시킬 수 없습니다.
    • X의 경우에도 한 줄 완성과 다를께 없기 때문에 동일한 코드로 한번에 검사했습니다.

PseudoCode

if(O개수가 X개수보다 많으면) invalid
else if(X개수가 O개수보다 2개이상 많으면) invalid
else if (X빙고가 1개 이상이면서 O빙고도 1개 이상이면) invalid
else if (X빙고가 1개 이상이면서 X개수가 O개수보다 1개 많으면) valid // X승
else if (O빙고가 1개 이상이면서 X개수와 O개수가 같으면) valid // O승
else if (X빙고와 O빙고가 없고 X개수가 O개수보다 1개 많으면) valid // 무승부
else invalid

정답

import java.io.*;

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		while (true) {
			String val = br.readLine();
			if (val.equals("end")) {
				break;
			}
			char[][] board = new char[3][3];
			int cnt = 0;
			int O_cnt = 0;
			int X_cnt = 0;
			int B_cnt = 0;
			for (int i = 0; i < 3; i++) {
				for (int j = 0; j < 3; j++) {
					board[i][j] = val.charAt(cnt++);
					if (board[i][j] == 'O') {
						O_cnt++;
					} else if (board[i][j] == 'X') {
						X_cnt++;
					} else {
						B_cnt++;
					}
				}
			}

			int XBingoCnt = bingo('X', board);
			int OBingoCnt = bingo('O', board);

			if (O_cnt > X_cnt) { // O는 X보다 많을 수 없습니다.
				System.out.println("invalid");
			} else if (X_cnt - O_cnt >= 2) { // X는 O와 같거나 1개 많을 수 있습니다.
				System.out.println("invalid");
			} else if (XBingoCnt >= 1 && OBingoCnt >= 1) { // X와 O가 동시에 빙고일 수 없습니다.
				System.out.println("invalid");
			} else if (XBingoCnt >= 1 && X_cnt - O_cnt == 1) { // X가 빙고인 상황
				System.out.println("valid");
			} else if (OBingoCnt >= 1 && X_cnt - O_cnt == 0) { // O가 빙고인 상황
				System.out.println("valid");
			} else if (XBingoCnt == 0 && OBingoCnt == 0 && B_cnt == 0 && X_cnt - O_cnt == 1) { // 무승부
				System.out.println("valid");
			} else { // 더 진행이 가능한데 안하는 상태
				System.out.println("invalid");
			}

		}

	}

	static class pos {
		int x;
		int y;

		public pos(int x, int y) {
			super();
			this.x = x;
			this.y = y;
		}

		@Override
		public String toString() {
			return "pos [x=" + x + ", y=" + y + "]";
		}
	}

	public static int bingo(char val, char[][] board) {
		int bingoCnt = 0;
		if (board[0][0] == val && board[0][1] == val && board[0][2] == val) {
			bingoCnt++;
		}
		if (board[1][0] == val && board[1][1] == val && board[1][2] == val) {
			bingoCnt++;
		}
		if (board[2][0] == val && board[2][1] == val && board[2][2] == val) {
			bingoCnt++;
		}

		if (board[0][0] == val && board[1][0] == val && board[2][0] == val) {
			bingoCnt++;
		}
		if (board[0][1] == val && board[1][1] == val && board[2][1] == val) {
			bingoCnt++;
		}
		if (board[0][2] == val && board[1][2] == val && board[2][2] == val) {
			bingoCnt++;
		}

		if (board[0][0] == val && board[1][1] == val && board[2][2] == val) {
			bingoCnt++;
		}
		if (board[0][2] == val && board[1][1] == val && board[2][0] == val) {
			bingoCnt++;
		}
		return bingoCnt;
	}

}

기타

• 반례를 찾기 위해 분노의 8중for문(모든 경우의 수 고려)을 돌렸지만 못찾았다.

틀렸던 이유

• 무승부 상황에서 XBingoCnt == 0 && OBingoCnt == 0를 고려하지 않아서 틀렸었다.
  • (XBingoCnt >= 1 && X_cnt - O_cnt != 1), (OBingoCnt >= 1 && X_cnt - O_cnt !=0)인 경우가 아직 걸러지지 않았다.
  • 고려여부에 따른 반례들 중 일부
    • XXOXOXOXO
    • XXOXOOOXX
    • XXOXOXOOX