구현 문제입니다.
‘O’, ‘X’ 및 ‘.’ 3*3 보드에 주어진 경우 보드의 조각이 tic-tac-toe 게임의 규칙에서 벗어나지 않는지 확인해야 합니다.
틱택토 게임의 규칙은 다음과 같습니다.
- ‘.’에 ‘O’와 ‘X’를 번갈아 배치합니다. 위치. (‘O’가 먼저 갑니다)
- ‘O’ 또는 ‘X’의 직선 길이가 3이 되면 게임이 종료됩니다.
즉, 두 번째 조건에 의해 보드 수그리고 길이가 3인 직선의 유무확인하여 판단할 수 있습니다.
‘O’와 ‘X’ 사이의 보드 수 차이는 항상 1 이내여야 합니다.
직선 판정의 조건은 다음과 같습니다.
- ‘O’와 ‘X’ 직선을 모두 만들 때
- 하나의 직선이 만들어지면 게임이 끝나기 때문입니다. 불가능한하다.
- ‘O’자 직선만 만들 때
- 첫 번째 공격은 ‘O’이므로 숫자는 ‘X’와 같을 수 없습니다.
- ‘X’의 직선만 만들 때
- ‘X’는 백홀이므로 ‘O’의 개수와 같아야 합니다.
- 직선을 만들 수 없을 때
- 게임이 끝나지 않았기 때문에 가능한하다.
(구현 코드)
import java.util.*;
class Solution {
private final int() dx = {-1, 1, 0, 0, -1, 1, 1, -1};
private final int() dy = {0, 0, -1, 1, -1, 1, -1, 1};
private int n;
public int solution(String() board) {
int answer = 0;
n = board.length;
int o = 0;
int x = 0;
for(int i=0; i<n; i++){
for(int j=0; j<n; j++){
if(board(i).charAt(j) == 'O'){
o++;
}else if (board(i).charAt(j) == 'X'){
x++;
}
}
}
// 'O'와 'X'의 말판 개수 차이는 무조건 1이내
if((o-x) <= 1 && (o-x)>=0){
// 길이가 3인 직선이 만들어질 수 없음
if(o < 3 && x < 3){
answer = 1;
} else {
boolean()() visited = new boolean(n)(n);
boolean oLine = false;
boolean xLine = false;
// bfs를 통해 직선 확인
for(int i=0; i<n; i++){
for(int j=0; j<n; j++){
if(!visited(i)(j)){
if(board(i).charAt(j) == 'O'){
if(!oLine) oLine = isLine(board, visited, 'O', i, j);
} else if(board(i).charAt(j) == 'X'){
if(!xLine) xLine = isLine(board, visited, 'X', i, j);
}
}
}
}
if(oLine && xLine){ // 1. 하나의 직선이 만들어지면 게임이 종료되기 때문에 불가능하다.
answer = 0;
}else if(oLine){ // 2. 'O'의 직선만 만들어질 때
// 선공이 'O'이기 때문에, X와 개수가 같아질 수 없다.
if(o == x){
answer = 0;
}else{
answer = 1;
}
}else if(xLine){ // 3. 'X'의 직선만 만들어질 때
// 'X'는 후공이기 때문에, O의 개수와 같아야 한다.
if(o > x){
answer = 0;
}else{
answer = 1;
}
} else { // 4. 직선이 만들어지지 않을 때
answer = 1;
}
}
} else {
answer = 0;
}
return answer;
}
private boolean isLine(String() board, boolean()() visited, char c, int x, int y){
Queue<Node> qu = new LinkedList<>();
qu.add(new Node(x, y, -1, 1));
while(!qu.isEmpty()){
Node cn = qu.poll();
// 길이가 3인 직선이 만들어질 때
if(cn.len == 3){
return true;
}
for(int i=0; i<8; i++){
int nx = cn.x + dx(i);
int ny = cn.y + dy(i);
if(!inRange(nx, ny) || board(nx).charAt(ny) != c || visited(nx)(ny)){
continue;
}
// 직선이 되기 위해서는 같은 방향이여야 함
if(cn.d == -1 || cn.d == i){
qu.add(new Node(nx, ny, i, cn.len+1));
}
}
}
return false;
}
private boolean inRange(int x, int y){
return (x>=0 && y>=0 && x<n && y<n);
}
private class Node{
int x, y, d, len;
Node(int x, int y, int d, int len){
this.x = x;
this.y = y;
this.d = d; // 방향
this.len = len; // 길이
}
}
}