BLOCKGAME 문제관련 질문입니다.

  • reiui9
    reiui9

    우선 책의 해법이랑 상관없이 풀었습니다.
    이해가 잘 안가서 제 방식대로 풀어봤는데요,
    우선 채워나가는 방향을 좌상에서 우하로 고정을 하고,
    플레이어가 번갈아기면 맵을 최대한 빈틈없이 채워나가는 방법입니다.
    마지막 플레이어가 첫 플레이어 이고 맵을 채워나갈 수 없을경우 실패를 반환하게 됩니다.
    즉 첫번 째 플레이어가 이길 수 있는 상황이 존재한다면 전체적으로 TRUE를 반환하는 방식입니다.

    그런데 막상 돌려보니 알고리즘이 어떻게든 TRUE를 반환하는 것을 볼 수 있었습니다. 특히 2번째 아무것도 없는 상황에선 절대로 LOSE를 반환하지 않았습니다.

    사실 책에서 설명하는 방식이 이해가 잘 안되는데 제가 어떤걸 놓치고있는지 알려주실 수 있을까요??

    #include <iostream>
    #include <fstream>
    #include <algorithm>
    #include <vector>
    #include <string>
    
    using namespace std;
    
    int shape[6][3][2] = {
        {
            { 0,0 }, // | 모양
            { 1,0 },
            {-1,-1}
        },{
            { 0,0 }, // - 모양
            { 0,1 },
            {-1,-1}
        },{
            { 0,0 }, // ㄴ 모양
            { 1,0 },
            { 1,1 }
        },{
            { 0,0 }, // |- 모양
            { 0,1 },
            { 1,0 }
        },{
            { 0,0 }, // ㄱ 모양
            { 0,1 },
            { 1,1 }
        },{
            { 0,1 }, // _| 모양
            { 1,0 },
            { 1,1 }
        },
    };
    /*
    void printMap(vector<string>& map) {
        cout << endl;
        for (int i = 0; i < 5; i++) {
            for (int j = 0; j < 5; j++) {
                cout << map[i][j];
            }
            cout << endl;
        }
    }
    */
    
    bool coverMap(int cover,int id, vector<string>& map,int row_,int col_) {
        if (cover == 1) {
            for (int i = 0; i < 3; i++) {
                int row = shape[id][i][0],newrow=row_+row;
                int col = shape[id][i][1],newcol=col_+col;
                if (row == -1) continue;
                if (newrow < 0 || newrow >= 5 || newcol < 0 || newcol >= 5) return false;
                if (map[newrow][newcol] == '#') return false;
            }
            for (int i = 0; i < 3; i++) {
                int row = shape[id][i][0], newrow = row_ + row;
                int col = shape[id][i][1], newcol = col_ + col;
                if (row == -1) continue;
                map[newrow][newcol] = '#';
            }
            return true;
        }
        else {
            for (int i = 0; i < 3; i++) {
                int row = shape[id][i][0], newrow = row_ + row;
                int col = shape[id][i][1], newcol = col_ + col;
                if (row == -1) continue;
                map[newrow][newcol] = '.';
            }
            return true;
        }
    }
    
    bool playGame(int isOdd, vector<string> map,int row,int col) {
        if (col == 5) { row++; col = 0; }  // 채워나가는 순서를 고정한다 : 좌상 -> 우하
        if (row == 5) {
            if (isOdd==1)
                return false; // 마지막 남은 플레이어가 첫번째 플레이어일 경우 실패
            else 
                return true;
        }
        bool ck = false;
        for (int i = 0; i < 6; i++) {
            if (coverMap(1, i, map,row,col)) { // 해당 블럭으로 덮음
                ck = true;
                if (playGame((1 + isOdd) % 2, map, row, col + 1)) // 한칸 이동하여 재귀
                    return true;
                coverMap(0, i, map,row,col); // 덮은 블럭을 다시 회수
    
            }
        }
        if (ck)
            return false;
        else 
            return playGame(isOdd, map, row, col + 1); // 해당 칸에서 덮을 경우가 없는경우 플레이어를 안바꾸고 진행 
    }
    
    int main() {
        ifstream fin;
        fin.open("BLOCKGAME.txt");
        int T;
        fin >> T;
        fin.get();
        for (int test = 0; test < T; test++) {
            vector<string> map(5);
            for (int i = 0; i < 5; i++) 
                getline(fin, map[i]);
    
            if (playGame(1,map,0,0))
                cout << "WINNING" << endl;
            else
                cout << "LOSING" << endl;
        }
        fin.close();
        system("pause");
        return 0;
    }
    

    8년 전
0개의 댓글이 있습니다.
  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.