public class TicSolver
{
char[][] board;
char ch;
int[] y1 = {0,0,2,2,1,0,0,0};
int[] x1 = {0,2,2,0,0,1,0,2};
int[] y2 = {0,1,2,1,1,1,1,1};
int[] x2 = {1,2,1,0,1,1,1,1};
int[] y3 = {0,2,2,0,1,2,2,2};
int[] x3 = {2,2,0,0,2,1,2,0};
boolean checkInvalid () {
boolean O3=false, X3=false;
int O=0, X=0;
for (int i=0; i < 3; i++) {
for (int j=0; j < 3; j++) {
if(board[i][j] == 'O') O++;
else if(board[i][j] == 'X') X++;
}
}
for(int i=0; i < 8; i++)
if(board[y1[i]][x1[i]]=='O' && board[y2[i]][x2[i]]=='O' && board[y3[i]][x3[i]]=='O') {O3=true; break;}
for(int i=0; i < 8; i++)
if(board[y1[i]][x1[i]]=='X' && board[y2[i]][x2[i]]=='X' && board[y3[i]][x3[i]]=='X') {X3=true; break;}
if(O==X+1) ch = 'X';
if(O==X && !O3) return false;
else if(O==X+1 && !X3) return false;
return true;
}
boolean checkWin (char ch) {
for (int i=0; i < 8; i++)
if(board[y1[i]][x1[i]]==ch && board[y2[i]][x2[i]]==ch && board[y3[i]][x3[i]]==ch) return true;
return false;
}
void selectSpot(char ch) {
// 1. Win
for (int i=0; i < 8; i++) {
int cnt=0, spot=0, a=0, b=0;
if(board[y1[i]][x1[i]] == ch) cnt++;
else if(board[y1[i]][x1[i]] == '.') {spot++; a=y1[i]; b=x1[i];}
if(board[y2[i]][x2[i]] == ch) cnt++;
else if(board[y2[i]][x2[i]] == '.') {spot++; a=y2[i]; b=x2[i];}
if(board[y3[i]][x3[i]] == ch) cnt++;
else if(board[y3[i]][x3[i]] == '.') {spot++; a=y3[i]; b=x3[i];}
if(cnt==2 && spot==1) {board[a][b] = ch; return;}
}
// 2. Defense
for (int i=0; i < 8; i++) {
char other = (ch == 'O') ? 'X' : 'O';
int cnt=0, spot=0, a=0, b=0;
if(board[y1[i]][x1[i]] == other) cnt++;
else if(board[y1[i]][x1[i]] == '.') {spot++; a=y1[i]; b=x1[i];}
if(board[y2[i]][x2[i]] == other) cnt++;
else if(board[y2[i]][x2[i]] == '.') {spot++; a=y2[i]; b=x2[i];}
if(board[y3[i]][x3[i]] == other) cnt++;
else if(board[y3[i]][x3[i]] == '.') {spot++; a=y3[i]; b=x3[i];}
if(cnt==2 && spot==1) {board[a][b] = ch; return;}
}
// 3. Best choice
int a=0, b=0, priority=0, best=0, max=-1;
for (int i=0; i < 3; i++) {
for (int j=0; j < 3; j++) {
if (board[i][j] == '.') {
if (ch == 'O') {
if (i==0&&j==0 || i==0&&j==2 || i==2&&j==0 || i==2&&j==2) {
if(board[0][0]=='O' && (0==i||0==j)) priority=4;
else if(board[0][2]=='O' && (0==i||2==j)) priority=4;
else if(board[2][0]=='O' && (2==i||0==j)) priority=4;
else if(board[2][2]=='O' && (2==i||2==j)) priority=4;
else priority=3;
}
else if(i==1 && j==1) priority=2;
else priority=1;
}
else {
if(i==1 && j==1) priority=3;
else if(i==0&&j==1 || i==1&&j==0 || i==1&&j==2 || i==2&&j==1) priority=2;
else priority=1;
}
if(priority<best) continue;
else if(priority>best && best!=0) {best = priority; a=i; b=j; continue;}
int n=0;
board[i][j] = ch;
for (int k=0; k < 8; k++) {
int cnt=0, spot=0;
if(board[y1[k]][x1[k]] == ch) cnt++;
else if(board[y1[k]][x1[k]] == '.') spot++;
if(board[y2[k]][x2[k]] == ch) cnt++;
else if(board[y2[k]][x2[k]] == '.') spot++;
if(board[y3[k]][x3[k]] == ch) cnt++;
else if(board[y3[k]][x3[k]] == '.') spot++;
if(cnt==2 && spot==1) n+=2;
else if(cnt==1 && spot==2) n+=1;
}
board[i][j] = '.';
if(n>max) {best=priority; max=n; a=i; b=j;}
}
}
}
board[a][b] = ch;
}
public String whoWins(String[] sBoard) {
board = new char[3][3];
ch = 'O';
int spots=0;
for (int i=0; i < 3; i++)
board[i] = sBoard[i].toCharArray();
if(checkInvalid()) return "INVALID";
if(checkWin('O')) return "FIRST";
if(checkWin('X')) return "SECOND";
for (int i=0; i < 3; i++)
for (int j=0; j < 3; j++)
if(board[i][j] == '.') spots++;
// Test
while (spots-- > 0) {
selectSpot(ch);
if(checkWin(ch)) {
if(ch == 'O') return "FIRST";
else return "SECOND";
}
ch = (ch == 'O') ? 'X' : 'O';
}
return "DRAW";
}
}
Explanation
각 x,y 배열은 3칸을 검사하는데 필요한 인덱스를 순서대로 삽입한 것이다.
checkInvalid()
O와 X 개수를 센다. O==X이거나 O==X+1이면 정상이다. O==X 일 때 O가 빙고가 되거나, O==X+1 일 때 X가 빙고가 되면 invalid 이다.
selectSpot()
점에 내 패를 놓는 순서 : 1. 이길 경우 착점 2. 패 방지 착점 3. 최적의 수
3번은 가중치를 적용하였다. O와 X의 경우가 각각 다르다. O일 때는 선공이므로 (1. 꼭짓점 2. 가운데)를 점유하는 게 중요하고, X일 때는 후공이라 방어적이므로 (1.가운데 2.상하좌우)를 점유해야 한다.
가중치가 같을 경우, 각 경로에서 빙고를 할 수 있는 경우의 수가 높은 쪽이 선택된다.
*재귀를 쓰지 않고 풀었기 때문에 복잡하다. 재귀를 사용하는 다른 답을 참고하는 것이 간결하고 비슷하게 빠르다.
최근 덧글