algospot BLOCKGAME

문제 링크입니다: https://algospot.com/judge/problem/read/PROMISES

TICTACTOE(http://jaimemin.tistory.com/377?category=985009)와 비슷하게 보드의 모든 경우의 수를 미리 계산하고 푸는 문제였습니다.

인상적이였던 점은 보드를 5*5 이차원 배열로 표현하지 않고 비트 시프트 연산을 이용하여 25자리로 만들어 표현했다는 점이였습니다.

비록 보드가 비어있을 경우 160만가지의 경우의 수를 세야하기 때문에 속도는 조금 느리다해도 상당히 효율적인 코드인 것 같습니다.

#include <iostream>

#include <vector>

#include <bitset>

#include <cstring> //memset

using namespace std;

 

char cache[1 << 25];

vector<int> moves;

 

inline int cell(int y, int x) //좌표

{

        return 1 << (y * 5 + x); //쉬프트 연산 활용

}

 

//게임판에 놓을 수 있는 블록들의 위치를 미리 계산한다

void preCalculate(void)

{

        //세칸짜리 L자 모양 블록들을 계산

        //세칸짜리는 무조건 가로 세로 두칸씩 먹음

        for(int y=0; y<4; y++)

               for (int x = 0; x < 4; x++)

               {

                       vector<int> cells;

                       for (int dy = 0; dy < 2; dy++)

                              for (int dx = 0; dx < 2; dx++)

                                      cells.push_back(cell(y + dy, x + dx));

                       int square = cells[0] + cells[1] + cells[2] + cells[3]; //정사각형을 만들어

                       for (int i = 0; i << 4; i++)

                              moves.push_back(square - cells[i]); //하나의 칸을 빼주면 L자 모양

               }

        //두 칸짜리 블록들을 계산

        //두칸짜리는 가로가 한칸이라면 세로가 두칸, 세로가 한칸이라면 가로가 두칸

        for (int i = 0; i < 5; i++)

               for (int j = 0; j < 4; j++)

               {

                       moves.push_back(cell(i, j) + cell(i, j + 1));

                       moves.push_back(cell(j, i) + cell(j + 1, i));

               }

}

 

//현재 게임판 상태가 board일 때 현재 차례인 사람이 승리할지 여부를 판단

//(y, x)칸에 블록이 있다 -> (y*5+x)번 비트가 켜져 있다

char play(int board)

{

        //메모이제이션

        char &result = cache[board];

        if (result != -1)

               return result;

        result = 0;

        //모든 수 고려

        for (int i = 0; i < moves.size(); i++)

               //이 수를 이 게임판에 놓을 수 있는가 확인

               if((moves[i]&board)==0) //아직 보드에 놓여지지 않았고

                       if (!play(board | moves[i])) //게임판에 놓을 수 없는 경우

                       {

                              result = 1; //마지막으로 놓은 사람이 자신이므로 이겼다

                              break;

                       }

        return result;

}

 

int main(void)

{

        int test_case;

        cin >> test_case;

        if (test_case < 0 || test_case>50)

               exit(-1);

        preCalculate();

        for (int i = 0; i < test_case; i++)

        {

               memset(cache, -1, sizeof(cache));

               int board = 0;

               //보드 초기화

               for(int j=0; j<5; j++)

                       for (int k = 0; k < 5; k++)

                       {

                              char space;

                              cin >> space;

                              if (space == '#')

                                      board += cell(j, k);

                       }

               if (play(board))

                       cout << "WINNING" << endl;

               else

                       cout << "LOSING" << endl;

        }

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~

[참고] 프로그래밍 대회에서 배우는 알고리즘 문제해결전략