[백준 7682번] 틱택토 (JAVA)

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

7682번: 틱택토

 

 

문제

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

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

 

입력

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

 

출력

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

 

풀이

주어지는 것들로 조건을 찾아내어 걸어주며 탐색을 하면 되는 문제이다.

문제에 임의로 붙인 번호 순으로 뽑아낼 수 있는 조건들을 찾아보자.

여기서 한 사람의 말이 가로, 세로, 대각선 방향으로 놓는 데 성공하는 것을 빙고라고 하겠다.

 

1) 두 사람은 각각 X 또는 O 말을 번갈아가며 놓는데,

   - 게임판에 놓여지는 X와 O의 개수의 차이를 알 수 있다.

2) 반드시 첫 번째 사람이 X를 놓고 두 번째 사람이 O를 놓는다.

   - X가 하나 많거나, O와 개수가 같은 경우만 있을 수 있다. 차이가 그 이상과 이하가 되면 성립될 수 없다.

   - 먼저 놓는 X에게 유리한 게임이다. X가 무조건 이기거나 무승부일 것이다.

3) 한 사람의 말이 가로, 세로, 대각선 방향으로 3칸을 잇는 데 성공하면 게임은 즉시 끝난다.

   - 한 사람의 말이 가로, 세로, 대각선 중의 한 경우만 있어야 하고, 여러 개로 빙고가 되어 있으면 성립될 수 없다.

      ** 주어지는 테스트 케이스 2번은 마지막에 X를 정가운데 자리에 놓는다면 성립할 수 있다.

   - 게임판에 말이 가득 차지 않은 경우는 반드시 한 명의 말이 빙고를 이루고 있다.

   - 한 명이 빙고를 이루면 끝나기 때문에 둘 다 빙고인 경우는 없다.

4) 게임판이 가득 차도 게임은 끝난다.

   - 말이 꽉 채워진 경우에는 승부가 안 난채로 끝난 경우가 있을 수 있다.

 

위와 같이 찾을 수 있는 조건들을 최대한 찾아서 조건을 걸어주면 된다.

탐색 부분은 3*3 격자판이라 그냥 가로, 세로, 대각선을 조건 없이 편하게 탐색해주었다.

짧은 문제에서 조건들을 찾아내기 어렵기도 하고, 이해하는데 조금 오래 걸려서 까다로운 문제였다.

 

 

 

Code

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

public class Main {

	static char[][] board;

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

		StringBuilder sb = new StringBuilder();
		while(true) {
			String s = br.readLine();
			if(s.equals("end")) break;

			int xCnt = 0;
			int oCnt = 0;
			board = new char[3][3];
			for(int i=0; i<3; i++) {
				for(int j=0; j<3; j++) {
					board[i][j] = s.charAt(3*i+j);

					if(board[i][j]=='X') xCnt++;
					else if(board[i][j]=='O') oCnt++;
				}
			}
			//게임판이 꽉 채워졌을 때
			//X가 먼저 말을 놓았음으로 O보다 1개 무조건 많아야 한다.
			if(oCnt+xCnt==9 && xCnt-oCnt==1) {
				//한 명이 빙고를 완성하면 게임이 끝나기 때문에
                //둘 다 빙고가 성립될 수 없다.
				if(Check('X') && Check('O')) sb.append("invalid\n");
				//말이 꽉 채워진 경우에는 O가 이길 수 없다
				else if(Check('O')) sb.append("invalid\n");
				//X가 이긴 경우
				else sb.append("valid\n");
			}else{ //게임판이 꽉 채워지지 않은 경우
				//위와 동일하게 한 명이 빙고가 되면 
                //끝나야해서 둘 다 빙고인 경우는 없다.
				if(Check('X') && Check('O')) sb.append("invalid\n");
				//X가 이겼을 땐, X가 선공이어서 무조건 O보다 하나 많아야 한다.
				else if(Check('X') && xCnt-oCnt==1) sb.append("valid\n");
				//O가 이겼을 땐, O가 후공이어서 X와 O의 크기가 같아야만 한다.
				else if(Check('O') && xCnt==oCnt) sb.append("valid\n");
				//아무도 이기지 않았는데 말이 다 채워지지 않는 경우는 불가능하다.
				else sb.append("invalid\n");
			}
		}
		System.out.println(sb.toString());
	}
	
	private static boolean Check(char tiktakto) {

		//가로가 성립할 때
		for(int i=0; i<3; i++) {
			int cnt = 0;
			for(int j=0; j<3; j++) {
				if(board[i][j]==tiktakto) cnt++;
			}
			if(cnt==3) return true;
		}
		//세로로 성립할 때
		for(int j=0; j<3; j++) {
			int cnt = 0;
			for(int i=0; i<3; i++) {
				if(board[i][j]==tiktakto) cnt++;
			}
			if(cnt==3) return true;
		}
		//대각선으로 성립할 때
		if(board[0][0]==tiktakto && board[1][1]==tiktakto 
        				&& board[2][2]==tiktakto) return true;
		if(board[0][2]==tiktakto && board[1][1]==tiktakto 
        				&& board[2][0]==tiktakto) return true;

		return false;
	}
}