[백준 17837][C++] 새로운 게임2 (Gold 2)

[문제보기]

  17937. 새로운 게임 2

17837번: 새로운 게임 2

 

[풀이과정]

Chess에 대한 정보를 담기 위해 CHESS 구조체 {체스 위치의 y, x, 방향 } 

그리고 map에 대한 정보를 담기 위해 MAP_INFO 구조체 {칸의 색깔, 각 칸의 체스 개수}

를 만들어서 사용했다.

 

전체적인 로직은

1. 체스 이동

2. 체스판에 체스 말이 4개 이상 쌓인 곳이 있는지 확인

이 된다.

 

0. for문을 사용해 게임의 턴의 수를 셌고, 1000보다 크게 올라가는 경우 '-1'를 반환하게 했다.

 

1. 체스 이동 / main(), Moving()

체스의 정보를 가지고 체스를 이동시키는데, 먼저 map을 확인하여 움직이려는 체스가 있는 칸에 체스가 얼마나 있는지 

확인을 하고, 1개만 있으면 temp에 자기 자신을 넣고, 2개 이상 있으면 temp에 자기 자신부터 마지막 체스까지

저장하고, map에는 temp에 저장된 체스를 지워준다.

 

그리고 체스의 방향으로 이동을 시켜주는데, 이때 체스판에 나가는 경우는 파란색과 동일하다고 했으므로, Moving() 함수의 color에 해당하는 파라미터 부분에 파란색(2)을 넣어주고, 아닌 경우 map[][]의 색깔을 넣어준다. 

Moving() 함수는 각 색깔에 맞게 체스를 이동시켜주는데, 파란색 부분에서 또다시 파란색이 나오거나, 체스판 바깥으로 

나갈 수 있거나, 방향을 바꿨을 때, 다른 색깔이 나올 수 있으므로 재귀를 통해 한번 더 검사를 해준다.

 

2. 4개 이상 겹쳐진 map 확인 / check()

map의 vector v의 사이즈를 통해 체스 말이 4개 이상 쌓인 곳이 있는지 확인을 해준다.

이 체크하는 부분은 턴이 진행되던 중에 말이 4개 이상 쌓여진 순간순간마다 확인을 해줘야 하므로 

턴에 해당하는 for문 안에 넣어준다.

 

[소스코드]

#include <iostream>
#include <vector>
using namespace std;

typedef struct _CHESS{
    int y;
    int x;
    int dir;
} CHESS;

typedef struct _MAP_INFO{
    //0: 흰색, 1: 빨강, 2: 파랑
    int color;
    vector<int> v;
} MAP_INFO;

int n, k;
MAP_INFO map[7][7];
CHESS Chess[11];
pair<int, int> movdir[5] = {{0,0}, {0, 1}, {0, -1}, {-1, 0}, {1, 0}};

void all_print(){
    cout << "\n";
    for(int i=1; i<=n; i++){
        for(int j=1; j<=n; j++){
            cout << map[i][j].v.size() << "  ";
        }
        cout << "\n";
    }
}

int Inverse_Dir(int d){
    if(d == 1) return 2;
    else if(d == 2) return 1;
    else if(d == 3) return 4;
    return 3;
}

void Moving(int idx, int nexty, int nextx, int y, int x, int color, vector<int> temp){
    if(color == 0){
        for(int i=0; i<temp.size(); i++){
            map[nexty][nextx].v.push_back(temp[i]);
            Chess[temp[i]].y = nexty;
            Chess[temp[i]].x = nextx;
        }
    }
    else if(color == 1){
        for(int i=temp.size()-1; i>=0; i--){
            map[nexty][nextx].v.push_back(temp[i]);
            Chess[temp[i]].y = nexty;
            Chess[temp[i]].x = nextx;
        }
    }
    else{
        int re_dir = Inverse_Dir(Chess[idx].dir);
        Chess[idx].dir = re_dir;
        nexty = y + movdir[re_dir].first;
        nextx = x + movdir[re_dir].second;
        if(nexty <= 0 || n < nexty || nextx <= 0 || n < nextx || map[nexty][nextx].color == 2){
            for(int i=0; i<temp.size(); i++){
                map[y][x].v.push_back(temp[i]);
            }
            return;
        }
        
        Moving(idx, nexty, nextx, y, x, map[nexty][nextx].color, temp);
    }
}

bool Check(){
    for(int i=1; i<=n; i++){
        for(int j=1; j<=n; j++){
            if(map[i][j].v.size() >= 4){
                return true;
            }
        }
    }

    return false;
}

int main(){
    cin >> n >> k;
    for(int i=1; i<=n; i++){
        for(int j=1; j<=n; j++){
            cin >> map[i][j].color;
        }
    }

    for(int i=1; i<=k; i++){
        int y, x, d;
        cin >> y >> x >> d;
        Chess[i].y = y;
        Chess[i].x = x;
        Chess[i].dir = d;

        map[y][x].v.push_back(i);
    }

    int turn;
    bool flag = true;
    for(turn=0; turn < 1001 && flag; turn++){
        flag = true;
        for(int i=1; i<=k; i++){
            int y = Chess[i].y;
            int x = Chess[i].x;
            int dir = Chess[i].dir;

            vector<int> temp;
            if(map[y][x].v.size() == 1){
                temp.push_back(i);
                map[y][x].v.pop_back();
            }
            else{
                for(int j=0; j<map[y][x].v.size(); j++){
                    if(map[y][x].v[j] == i){
                        for(int k=j; k<map[y][x].v.size(); k++){
                            temp.push_back(map[y][x].v[k]);
                        }
                        map[y][x].v.erase(map[y][x].v.begin()+j, map[y][x].v.end());
                    }
                }
            }

            int ny = y + movdir[dir].first;
            int nx = x + movdir[dir].second;

            if(0 < ny && ny <= n && 0 < nx && nx <= n){
                Moving(i, ny, nx, y, x, map[ny][nx].color, temp);
            }
            else{
                Moving(i, ny, nx, y, x, 2, temp);
            }

            if(Check() == true){
                flag = false;
                break;
            }
        }
    }

    if(turn > 1000){
        cout << -1;
        return 0;
    }
    cout << turn;
}

 

[해결 과정 중 실수한 부분]

이 문제를 풀면서는 실수한 부분이 너무 많았다.

1. 체스말이 움직이는 순간순간 check()로 확인을 해줘야 하는데, 턴이 한번 종료 할 때마다 check()확인

2. 변수 오타가 많았다.