🎐 문제 설명
틱택토는 두 사람이 하는 게임으로 처음에 3x3의 빈칸으로 이루어진 게임판에 선공이 "O", 후공이 "X"를 번갈아가면서 빈칸에 표시하는 게임입니다. 가로, 세로, 대각선으로 3개가 같은 표시가 만들어지면 같은 표시를 만든 사람이 승리하고 게임이 종료되며 9칸이 모두 차서 더 이상 표시를 할 수 없는 경우에는 무승부로 게임이 종료됩니다.
할 일이 없어 한가한 머쓱이는 두 사람이 하는 게임인 틱택토를 다음과 같이 혼자서 하려고 합니다.
혼자서 선공과 후공을 둘 다 맡는다.
틱택토 게임을 시작한 후 "O"와 "X"를 혼자서 번갈아 가면서 표시를 하면서 진행한다.
틱택토는 단순한 규칙으로 게임이 금방 끝나기에 머쓱이는 한 게임이 종료되면 다시 3x3 빈칸을 그린 뒤 다시 게임을 반복했습니다. 그렇게 틱택토 수 십 판을 했더니 머쓱이는 게임 도중에 다음과 같이 규칙을 어기는 실수를 했을 수도 있습니다.
"O"를 표시할 차례인데 "X"를 표시하거나 반대로 "X"를 표시할 차례인데 "O"를 표시한다.
선공이나 후공이 승리해서 게임이 종료되었음에도 그 게임을 진행한다.
게임 도중 게임판을 본 어느 순간 머쓱이는 본인이 실수를 했는지 의문이 생겼습니다. 혼자서 틱택토를 했기에 게임하는 과정을 지켜본 사람이 없어 이를 알 수는 없습니다. 그러나 게임판만 봤을 때 실제로 틱택토 규칙을 지켜서 진행했을 때 나올 수 있는 상황인지는 판단할 수 있을 것 같고 문제가 없다면 게임을 이어서 하려고 합니다.
머쓱이가 혼자서 게임을 진행하다 의문이 생긴 틱택토 게임판의 정보를 담고 있는 문자열 배열 board가 매개변수로 주어질 때, 이 게임판이 규칙을 지켜서 틱택토를 진행했을 때 나올 수 있는 게임 상황이면 1을 아니라면 0을 return 하는 solution 함수를 작성해 주세요.
♣ 제한사항
board의 길이 =board[i]의 길이 = 3board의 원소는 모두 "O", "X", "."으로만 이루어져 있습니다.
board[i][j]는i+ 1행j+ 1열에 해당하는 칸의 상태를 나타냅니다.- "."은 빈칸을, "O"와 "X"는 해당 문자로 칸이 표시되어 있다는 의미입니다.
🥎 풀이
이 문제의 핵심은 문제 예시에도 언급되어 있듯,
"실수를 했을 가능성이 있는가"를 묻는 게 아닌 "이 게임판이 규칙을 지켜서 진행한 틱택토에서 나올 수 있는 상황인가"
이다.
즉 규칙을 지켜서 진행이 가능한 경우가 한번이라도 나온다면 return 1 이 된다는 것이다.
문제 설명에서는
- "O"를 표시할 차례인데 "X"를 표시하거나 반대로 "X"를 표시할 차례인데 "O"를 표시한다.
- 선공이나 후공이 승리해서 게임이 종료되었음에도 그 게임을 진행한다.
위와 같은 두 가지의 경우 규칙을 어긴다고 나와있다.
나는 따라서 다음과 같은 경우에만 return 1 이 되어야 한다고 판단했다.
- 후공의 차례는 선공의 차례보다 적거나 같아야 하며, 선공의 차례는 후공과의 차례와 차이가 1 보다 많이 나서는 안된다.
- 선공, 후공 둘 중 한 경우에만 승리해야 한다.
- 두번 승리가 가능한 경우는 선공 뿐이다.
이에 대해서는 다음과 같이 설명할 수 있다.
1. 후공의 차례는 선공의 차례보다 적거나 같아야 하며, 선공의 차례는 후공과의 차례와 차이가 1 보다 많이 나서는 안된다.
후공의 차례가 선공의 차례보다 많은 경우는 규칙에 어긋나는 행위이다.
또한 선공의 차례가 1 초과 차이나는 경우 또한 동일하다.
따라서 선공, 후공의 차례의 수를 먼저 센 후 위의 경우 바로 return 0 을 할 수 있도록 했다.
2. 선공, 후공 둘 중 한 경우에만 승리해야 한다.
선공이 승리한 경우와, 후공이 승리한 경우를 나누어 찾아주어야 한다.
선공이 승리한 경우
→ 선공이 놓은 차례가 후공이 놓은 차례보다 무조건 1번 많다.
→ 같거나 그 이상 많은 경우는 승리 이후 게임을 진행했다는 것이므로 옳지 않다.후공이 승리한 경우
→ 선공이 놓은 차례와 후공이 놓은 차례가 무조건 갯수가 같아야 한다.
→ 선공이 놓은 차례가 후공 보다 많은 경우 혹은 후공 차례가 더 많은 경우 후공이 승리한 이후에도 게임을 진행했다는 의미가 된다. (또한 후공의 차례가 더 많을 수는 없다)
3. 두번 승리가 가능한 경우는 선공 뿐이다.
다음과 같은 경우 선공은 두번 승리 가 가능하다.
이렇게 되는 경우는 선공이 무조건 5번 차례를 지내는 경우만 가능하다.
따라서 선공이 5번 인지를 체크 해야 한다.
👝 코드
#include <string>
#include <vector>
#include <iostream>
using namespace std;
vector<pair<int, int> > dir = {
make_pair(-1, 0),
make_pair(-1, 1),
make_pair(0, 1),
make_pair(1, 1),
make_pair(1, 0),
make_pair(1, -1),
make_pair(0, -1),
make_pair(-1, -1)
};
int isWin(int y, int x, char turn, vector<string> board);
int solution(vector<string> board) {
int answer = 1;
int allX = 0, allO = 0, winO = 0, winX = 0;
// Count X, O
for (string s:board) {
for (int i = 0; i < s.length(); i++) {
if (s[i] == 'X') allX += 1;
else if (s[i] == 'O') allO += 1;
}
}
// if X > O or O > X + 1 : return 0
if (allX > allO || allO - allX > 1) return 0;
// check Win
for (int i = 0; i < board.size(); i++) {
for (int j = 0; j < board.size(); j++) {
if (board[i][j] == 'O') {
winO += isWin(i, j, 'O', board);
if (winX && winO) return 0;
}
else if (board[i][j] == 'X') {
winX += isWin(i, j, 'X', board);
if (winO && winX) return 0;
}
}
}
if (((winX == winO) && (winO == 0)) || ((winX / 2 == 1) && (allO == allX)) || ((winO / 2 == 1) && (allO - allX == 1)) || ((allO == 5) && (winO / 2 == 2))) return 1;
else return 0;
}
int isWin(int y, int x, char turn, vector<string> board) {
int cnt = 0;
for (int d = 0; d < 8; d++) {
int i;
for (i = 1; i <= 2; i++) {
int nextY = y + (dir[d].first * i), nextX = x + (dir[d].second * i);
if ((nextX >= 0 && nextX < 3) && (nextY >= 0 && nextY < 3)) {
if (board[nextY][nextX] != turn) break;
}
else break;
}
if (i == 3) cnt += 1;
}
return cnt;
}👜 어려웠던 점
- 규칙에 어긋나는 경우에 대한 반례 찾기
→ 어떠한 경우에 규칙에 어긋나는지 찾는 부분에서 오래걸렸다 . . - 효율 문제
→ 효율적인 부분을 계속해서 고민하다 보니 대부분의 문제에서 막막함을 느꼈다. 일단은 문제 해결에 집중해야할 것 같다.
