혼자서 하는 틱택토 (Programmers Lv.2)

문제

...
머쓱이가 혼자서 게임을 진행하다 의문이 생긴 틱택토 게임판의 정보를 담고 있는 문자열 배열 board가 매개변수로 주어질 때, 이 게임판이 규칙을 지켜서 틱택토를 진행했을 때 나올 수 있는 게임 상황이면 1을 아니라면 0을 return 하는 solution 함수를 작성해 주세요.

https://school.programmers.co.kr/learn/courses/30/lessons/160585

 

풀이

해당 문제를 다시 복습한 이유는 기본에 충실해서!!!

내가 생각하기에 브루트포스(Bruteforce)와 백트래킹(Backtracking)의 정석과도 같은 문제라 판단해서 다시 살펴보는 시간을 가져보았다!

 

C++ 풀이)

#include <string>
#include <vector>

using namespace std;

vector<vector<string>> allCases;

bool equal(char a, char b, char c) {
    return a == b && b == c;
}

bool gameEnd(vector<string> board) {
    for(int i = 0; i < 3; i++) {
        if(equal(board[i][0], board[i][1], board[i][2]) && board[i][0] != '.')
            return true;
    }
    for(int i = 0; i < 3; i++) {
        if(equal(board[0][i], board[1][i], board[2][i]) && board[0][i] != '.')
            return true;
    }
    if(equal(board[0][0], board[1][1], board[2][2]) && board[0][0] != '.')
        return true;
    if(equal(board[0][2], board[1][1], board[2][0]) && board[1][1] != '.')
        return true;
    
    return false;
}

char nextTurn(char turn) {
    if(turn == 'O')
        return 'X';
    else
        return 'O';
}

void bruteforce(int cnt, char turn, vector<string> board) {
    allCases.push_back(board);
    
    if(cnt == 9 || gameEnd(board))
        return;
    
    for(int i = 0; i < 9; i++) {
        int r = i / 3;
        int c = i % 3;
        
        if(board[r][c] != '.')
            continue;
        
        // 백트래킹
        board[r][c] = turn;
        bruteforce(cnt + 1, nextTurn(turn), board);
        board[r][c] = '.';
    }
}

bool sameCase(vector<string> &a, vector<string> &b) {
    for(int i = 0; i < 3; i++) {
        for(int j = 0; j < 3; j++) {
            if(a[i][j] != b[i][j])
                return false;
        }
    }
    
    return true;
}

int solution(vector<string> board) {
    vector<string> initBoard;
    for(int i = 0 ; i < 3; i++)
        initBoard.push_back("...");
    // 브루트 포스로 모든 경우의 수 구하기
    bruteforce(0, 'O', initBoard);
    
    for(auto canCase: allCases) {
        if (sameCase(board, canCase))
            return 1;
    }
    
    return 0;
}

 

 

JS 풀이)

const allCases = [];

function isEqual(a, b, c) {
    return a === b && b === c;
}
    
function finishGame(board) {
    for(let i = 0; i < 3; i++) {
        if(isEqual(board[i][0], board[i][1], board[i][2]) && board[i][0] !== '.')
            return true;
    }

    for(let i = 0; i < 3; i++) {
        if(isEqual(board[0][i], board[1][i], board[2][i]) && board[0][i] !== '.')
            return true;
    }

    if(isEqual(board[0][0], board[1][1], board[2][2]) && board[0][0] !== '.')
            return true;
    if(isEqual(board[0][2], board[1][1], board[2][0]) && board[1][1] !== '.')
            return true;

    return false;
}

function nextTurn(turn) {
    return turn === 'O' ? 'X' : 'O';
}

function bruteforce(cnt, turn, board) {
    allCases.push(board.map(row => [...row]));
    
    if(cnt === 9 || finishGame(board))
        return;
    
    for(let i = 0; i < 9; i++) {
        let r = Math.floor(i / 3);
        let c = i % 3;
        
        if(board[r][c] !== '.')
            continue;
        
        // 백트래킹
        board[r][c] = turn;
        bruteforce(cnt + 1, nextTurn(turn), board);
        board[r][c] = '.';
    }
}

function isSame(a, b) {
    for(let i = 0; i < 3; i++) {
        for(let j = 0; j < 3; j++) {
            if(a[i][j] !== b[i][j])
                return false;
        }
    }
    
    return true;
}

function solution(board) {
    let answer = 0;
    
    const initBoard = [['.', '.', '.'], ['.', '.', '.'], ['.', '.', '.']];
    
    // 브루트 포스로 모든 경우의 수 체크
    bruteforce(0, 'O', initBoard);
    
    for(const curCase of allCases) {
        if(isSame(curCase, board)) {
            answer = 1;
            break;
        }
    }
    
    return answer;
}