백준 7682. 틱택토

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

7682번: 틱택토

 

처음에 백트래킹 문제인가 싶었는데, 게임의 완성 조건을 판별하는 문제였다.

 

1. X가 먼저 시작하기 때문에 X의 돌의 갯수는 O의 돌의 갯수와 같거나 딱 1개 많아야 한다.

 

2. X또는 O가 1줄 빙고 일때, 다른 한쪽이 빙고여선 안된다.

예를들어 다음과 같은 경우는 invalid다.

. O X

X O X

. O X

 

3. 판이 꽉찼을때는 X의 갯수가 5개 && O의 갯수가 4개 인경우 && X 1줄 빙고인 경우 밖에 없다.

예를들어 다음과 같은 경우는 invalid 다. 

OXX

XOO

XOO

 

OXX

XOX

XXO 

=> 이 경우는 X가 먼저 시작하기 때문에, O 빙고가 만들어졌을때 게임이 끝났어야 한다.