틱택토 (백준 7682)

문제

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

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

입력

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

출력

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

예제 입력 1

XXXOO.XXX
XOXOXOXOX
OXOXOXOXO
XXOOOXXOX
XO.OX...X
.XXX.XOOO
X.OO..X..
OOXXXOOXO
end

예제 출력 1

invalid
valid
invalid
valid
valid
invalid
invalid
invalid

---

🚀문제 해석

입력값이 게임이 끝난 최종 상태이다. 따라서 최종 상태는 세가지 경우 중 하나에 해당하게 된다.

1. X가 이긴 경우
2. O가 이긴 경우
3. 판이 가득 찬 경우

X가 이긴 경우는 X의 갯수가 O보다 하나 커야된다. 그리고 O으로 이루어진 틱택토가 존재하면 안되고 틱택토를 하나 만들면 게임이 종료되기 때문에 X로 만든 틱택토는 하나만 있어야한다.

 

반대로 O가 이긴경우에는 X의 갯수와 O의 갯수가 같아야한다. 그리고 X으로 이루어진 틱택토는 존재하지 않으며 O로 만들어진 틱택토는 한 개 뿐이어야한다.

 

판이 가득 찬 경우에는 X를 O보다 먼저 두기 때문에 X의 갯수는 5개, O의 갯수는 4개를 만족해야한다.

 

🛠코드

function checkX(map) {
  for (let i = 0; i < 3; i++) {
    // 가로 체크
    if (map[i][0] === 'X' && map[i][0] === map[i][1] && map[i][1] === map[i][2]) return true;
    // 세로 체크
    if (map[0][i] === 'X' && map[0][i] === map[1][i] && map[1][i] === map[2][i]) return true;
  }
  // 대각선 체크
  if (map[0][0] === 'X' && map[0][0] === map[1][1] && map[1][1] === map[2][2]) return true;
  if (map[0][2] === 'X' && map[0][2] === map[1][1] && map[1][1] === map[2][0]) return true;

  return false;
}

function checkO(map) {
  for (let i = 0; i < 3; i++) {
    // 가로 체크
    if (map[i][0] === 'O' && map[i][0] === map[i][1] && map[i][1] === map[i][2]) return true;
    // 세로 체크
    if (map[0][i] === 'O' && map[0][i] === map[1][i] && map[1][i] === map[2][i]) return true;
  }
  // 대각선 체크
  if (map[0][0] === 'O' && map[0][0] === map[1][1] && map[1][1] === map[2][2]) return true;
  if (map[0][2] === 'O' && map[0][2] === map[1][1] && map[1][1] === map[2][0]) return true;

  return false;
}

function solution() {
  let boards = require('fs')
    .readFileSync(0)
    .toString()
    .trim()
    .split('\n')
    .map((elem) => elem.trim());

  for (const board of boards) {
    if (board === 'end') break;
    let map = Array.from({ length: 3 }, () => Array.from({ length: 3 }).fill(0));
    for (let i = 0; i < board.length; i++) {
      map[Math.floor(i / 3)][i % 3] = board[i];
    }
    let xCnt = 0;
    let oCnt = 0;
    for (let i = 0; i < map.length; i++) {
      for (let j = 0; j < map[0].length; j++) {
        if (map[i][j] === 'X') xCnt++;
        else if (map[i][j] === 'O') oCnt++;
      }
    }

    let isX = checkX(map);
    let isO = checkO(map);

    if (isX && !isO && xCnt === oCnt + 1) console.log('valid');
    else if (!isX && isO && xCnt === oCnt) console.log('valid');
    else if (!isX && !isO && xCnt === 5 && oCnt === 4) console.log('valid');
    else console.log('invalid');
  }
}
solution();

 

📝참고자료

https://howudong.tistory.com/254

[C++] 백준/BOJ - 7682 : 틱택토