👓 문제 설명
틱택토 게임은 두 명의 사람이 번갈아가며 말을 놓는 게임이다. 게임판은 3×3 격자판이며, 처음에는 비어 있다. 두 사람은 각각 X 또는 O 말을 번갈아가며 놓는데, 반드시 첫 번째 사람이 X를 놓고 두 번째 사람이 O를 놓는다. 어느 때든지 한 사람의 말이 가로, 세로, 대각선 방향으로 3칸을 잇는 데 성공하면 게임은 즉시 끝난다. 게임판이 가득 차도 게임은 끝난다.
게임판의 상태가 주어지면, 그 상태가 틱택토 게임에서 발생할 수 있는 최종 상태인지를 판별하시오.
💣 제한 사항
- 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 줄은 9개의 문자를 포함하며, 'X', 'O', '.' 중 하나이다.
- '.'은 빈칸을 의미하며, 9개의 문자는 게임판에서 제일 윗 줄 왼쪽부터의 순서이다. 입력의 마지막에는 문자열 "end"가 주어진다.
- 각 테스트 케이스마다 한 줄에 정답을 출력한다. 가능할 경우 "valid", 불가능할 경우 "invalid"를 출력한다.
🚨 접근 방법
주어진 입력이 틱택토 게임에서 최종 상태로 가능한지 판별하는 문제이다.
가능한 경우는 다음과 같다.
- 틱택토 X가 완성된 경우
- 틱택토 O가 완성된 경우
- 3x3의 게임판이 모두 찬 경우
이외의 경우는 모두 불가능하다.
1의 경우는 X로 1줄 이상(가로, 세로, 대각 포함)이고, O로 0줄, X가 O보다 1개 많을 때 가능하다.
2의 경우는 O로 1줄 이상(가로, 세로, 대각 포함)이고, X로 0줄, X가 O과 개수가 동일할 때 가능하다.
3의 경우는 X가 5개, O가 4개, X와 O 모두 0줄일 때 가능하다.
처음 제출 했을 때는 X와 O가 모두 1줄일 때만 가능하다고 판단했다.
그러나 테스트 케이스 10%에서 틀리게 되었고,
반례를 찾아보았을 때 다음과 같았다.
XOO
XOO
XXX
마지막에 (2,0)에 X를 놓을 경우
X가 2줄이 생기는 경우가 있었다.
이미 X가 O보다 1개 많을 때로 조건을 채워놓았으니
X가 1줄일 때만 만족하는게 아니라 1줄 이상일 때 만족을 해야 가능했다.
🚈 풀이
#include<iostream>
using namespace std;
bool func(string s) {
int cnt_x = 0, cnt_o = 0;
// x,o 개수 카운트
for (int i = 0; i < s.length(); i++) {
if (s[i] == 'X')cnt_x++;
if (s[i] == 'O')cnt_o++;
}
// x가 2개 이상 많거나 o가 더 많은 경우 false
if (cnt_x - cnt_o > 1)return false;
if (cnt_o - cnt_x > 0)return false;
int cnt_x_line = 0, cnt_o_line = 0;
// 가로
for (int i = 0; i < 7; i += 3) {
if (s[i] != '.') {
if (s[i] == s[i + 1] && s[i + 1] == s[i + 2]) {
if (s[i] == 'X')cnt_x_line++;
else if (s[i] == 'O')cnt_o_line++;
}
}
}
// 세로
for (int i = 0; i < 3; i ++) {
if (s[i] != '.') {
if (s[i] == s[i + 3] && s[i + 3] == s[i + 6]) {
if (s[i] == 'X')cnt_x_line++;
else if (s[i] == 'O')cnt_o_line++;
}
}
}
int cnt_x_cross = 0, cnt_o_cross = 0;
// 대각
// 대각은 2개가 생겨도 가운데 하나 빼면 2개를 상쇄가 가능
bool check = false;
if (s[0] != '.') {
if (s[0] == s[4] && s[4] == s[8]) {
check = true;
if (s[0] == 'X')cnt_x_cross++;
else if (s[0] == 'O')cnt_o_cross++;
}
}
if (s[2] != '.') {
if (s[2] == s[4] && s[4] == s[6]&& !check) {
if (s[2] == 'X')cnt_x_cross++;
else if (s[2] == 'O')cnt_o_cross++;
}
}
int sum_x = cnt_x_cross + cnt_x_line;
int sum_o = cnt_o_cross + cnt_o_line;
// x의 틱택토 성공
if (sum_x > 0 && sum_o == 0 && cnt_x - cnt_o == 1) {
return true;
}
// y의 틱택토 성공
if (sum_o > 0 && sum_x == 0 && cnt_x - cnt_o == 0) {
return true;
}
// 모든 칸이 채워질 때
if ((sum_x + sum_o) == 0 && cnt_x == 5 && cnt_o == 4)return true;
return false;
}
int main() {
string s;
while (1) {
cin >> s;
if (s == "end")break;
if (func(s))cout << "valid" << "\n";
else cout << "invalid" << "\n";
}
return 0;
}