예제: 틱택토
틱택토는 3x3 크기의 게임판에서 하는 3목 게임입니다. 두 명이 번갈아가며 o와 x를 게임판의 빈 칸에 쓰되, 먼저 같은 글자를 가로, 세로 혹은 대각선으로 3개 쓰이도록 하는 쪽이 이깁니다. 예를 들어, 다음 게임판은 x가 이긴 게임판입니다.
xoo .x. ..x게임은 항상 x부터 시작합니다.
틱택토 게임판의 현재 상태가 주어집니다. 두 사람 모두 최선을 다한다고 가정할 때, 어느쪽이 이길지 판단하는 프로그램을 작성하세요.
입력
입력의 첫 줄에는 테스트 케이스의 수 C(<= 50)가 주어집니다. 각 테스트 케이스는 세 줄에 각 세 글자로 게임판의 각 위치에 쓰인 글자가 주어집니다. 글자가 없는 칸은 마침표(.)로 표현합니다.출력
각 테스트 케이스마다 한 줄을 출력합니다. 두 사람이 모두 최선을 다할 경우 비긴다면 TIE를, 아닌 경우 이기는 사람의 글자를 출력합니다.예제 입력
3 ... ... ... xx. oo. ... xox oo. x.x예제 출력
TIE x o
풀이
이게 무슨 난이도 하란 말인가!!! 체감 난이도는 중 이상이었다.
사실 이해하고 나서 풀어보니 하가 맞는것도 같지만, 문제 자체를 이해하기가 어려웠다.
우선은, 게임은 'x'부터 시작하는게 아니다. 'x'가 먼저 시작했기 때문에, 보드에 놓인 'x'의 개수가 'o'의 개수보다 적거나 같으면 다음 차례는 'x'이고, 아니면 'o'이다.
또, 예를 들어 특정 위치에 'x'를 놓았을 경우, 그 다음 일어날 수 있는 경우의 수에 대해서 'x'가 이기는 경우가 하나라도 있다면 'x'가 이긴 경우를 return하고, 비기거나 'o'가 이긴 경우 비긴 경우를 return하는 방식으로 로직을 만들어야 한다.
다이나믹 프로그래밍을 사용하기 위해 보드에 놓일 수 있는 모든 경우의 수를 3진수로 계산하여 cache와 mapping한것도 새로웠다.
코드는 길고 복잡해 보이지만, 중심이 되는 isWin() 함수를 그렇게 복잡하지는 않은 문제였다.
전체적인 소스코드는 아래와 같다.
소스 코드
#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
char board[3][3];
int cache[19683];
//board 확인해서 승부가 났는지 리턴하는 함수
//x가 이기면 1, o가 이기면 2, 아니면 0을 리턴한다.
int isGameEnd() {
//가로
bool gameEnd;
for (int y = 0; y < 3; y++) {
gameEnd = true;
for (int x = 0; x < 2; x++) {
if (board[y][x] == '.' || board[y][x] != board[y][x + 1]) {
gameEnd = false;
break;
}
}
if (gameEnd) {
return board[y][0] == 'x' ? 1 : 2;
}
}
//세로
gameEnd = true;
for (int x = 0; x < 3; x++) {
gameEnd = true;
for (int y = 0; y < 2; y++) {
if (board[y][x] == '.' || board[y][x] != board[y + 1][x]) {
gameEnd = false;
break;
}
}
if (gameEnd) {
return board[0][x] == 'x' ? 1 : 2;
}
}
//대각선
if (board[0][0] != '.' && board[0][0] == board[1][1] && board[1][1] == board[2][2]) return board[0][0] == 'x' ? 1 : 2;
if (board[0][2] != '.' && board[0][2] == board[1][1] && board[1][1] == board[2][0]) return board[0][2] == 'x' ? 1 : 2;
return 0;
}
//cache에 맵핑할 인덱스를 생성하는 함수.
int toIndex() {
int idx = 0;
for (int y = 0; y < 3; y++) {
for (int x = 0; x < 3; x++) {
idx += pow(3, 3 * y + x) * (board[y][x] == 'x' ? 1 : board[y][x] == 'o' ? 2 : 0);
}
}
return idx;
}
int isWin(char turn) {
if (isGameEnd()) return isGameEnd();
int& res = cache[toIndex()];
if (res != -1) return res;
res = 3;
for (int y = 0; y < 3; y++) {
for (int x = 0; x < 3; x++) {
if (board[y][x] == '.') {
board[y][x] = turn;
int result = isWin('x' + 'o' - turn);
if (turn == 'x') {
if (result == 1) res = 1;
else if(res != 1) res = min(res, result);
}
else if (turn == 'o') {
if (result == 2) res = 2;
else if (res != 2) res = min(res, result);
}
board[y][x] = '.';
}
}
}
if (res == 3) return res = 0;
return res;
}
int main() {
int testCase;
cin >> testCase;
for (int tc = 0; tc < testCase; tc++) {
memset(cache, -1, sizeof(cache));
int xc = 0, oc = 0;
for (int y = 0; y < 3; y++) {
for (int x = 0; x < 3; x++) {
cin >> board[y][x];
if (board[y][x] == 'x') xc++;
if (board[y][x] == 'o') oc++;
}
}
int res = isWin(xc <= oc ? 'x' : 'o');
cout << (res == 0 ? "TIE" : res == 1 ? "x" : "o") << endl;
}
return 0;
}풀이 후기
필자가 푼 방법과 도서의 해법은 풀이 시간이 차이가 많이 났는데, 필자가 푼 방법이 훨씬 느렸다.
이유를 생각해 보면, 필자는 비기는 경우를 0, 'x'가 이기는 경우를 1, 'o'가 이기는 경우를 2로 리턴하였기 때문에 결과를 저장하는 과정에서 'x'인지 'o'인지 일일이 따져야 하고, 조건문이 늘어나는 경우가 발생했다.
반면 도서풀이의 경우는 현재 상태가 'x'인지 'o'인지 관여하지 않고(아예 신경쓰지 않는다는 것은 아닌다.) 다음 상태의 결과를 이기는 경우 1, 비기는 경우 0, 지는 경우 -1을 리턴하므로써 조건문을 많이 줄일 수 있었다.
이번 문제는 필자에게는 생소하고 어렵기도 한 문제였지만, 디테일의 차이 또한 느껴지는 문제였다.
