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

https://www.acmicpc.net/problem/17837

17837번: 새로운 게임 2

---

새로운 게임은 게임 규칙에 따라 코드를 작성해주시면 되며,

각 칸 위에 놓인 말들을 저장하는 벡터의 2차원 배열로 구현하였습니다.

단, 주의할 점이 몇가지 있습니다.

 

⚠️ 주의할 점

1. 다음 칸이 파란색인 경우, 방향을 반대로 바꾼 후, 이동하려는 칸이 파란색이거나 체스판을 벗어나는 경우 움직이지 않아야 한다.
2. 다음 칸이 파란색인 경우 방향을 반대로 바꾼 후, 이동하려는 칸이 빨간색인 경우 말을 이동시키고, 말이 쌓여있는 순서를 바꾸어야 한다.
3. 말을 움직일 때마다 쌓인 말의 개수를 체크해주어야 한다.
4. 2차원 배열을 순회하면서 th번째 말을 이동시킨 경우, th를 증가시켜야한다. (ex. 방향이 1인 (1, 1) 위의 1번째 말을 이동시킨 경우 (1, 2)로 이동함, 하지만 th가 1인 채 2차원 배열을 계속 순회하는 경우, (1, 2) 위의 1번째 말이 반복해서 이동할 수 있음)

 

아래는 전체 코드입니다.

#include <bits/stdc++.h>
using namespace std;

#define x first
#define y second

typedef struct{int x, y, th, dir;} piece;   // 말의 정보를 나타내는 구조체
int dx[4] = {0, 0, -1, 1};
int dy[4] = {1, -1, 0, 0};
int board[12][12];
int n, m;

void move(vector<piece> pieces[][12], pair<int, int> cur, pair<int, int> nx, int th){ // cur 위치에 있는 th번째 말과 위에 올려져 있는 말들을 nx로 이동시키는 함수
    for(auto iter = pieces[cur.x][cur.y].begin() + th; iter != pieces[cur.x][cur.y].end();){ // th번째 말부터 nx 위치에 쌓음
        (*iter).x = nx.x; (*iter).y = nx.y; // 말의 좌표 수정
        pieces[nx.x][nx.y].push_back((*iter));  // nx 위치에 쌓음
        iter = pieces[cur.x][cur.y].erase(iter);    // 현재 위치의 말 제거
    }
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> m;
    for(int i = 0; i < n; i++)
        for(int j = 0; j < n ; j++)
            cin >> board[i][j];
    
    vector<piece> pieces[12][12];
    for(int i = 0; i < m; i++){
        piece p; cin >> p.x >> p.y >> p.dir;
        p.th = i;
        p.x--; p.y--; p.dir--;
        pieces[p.x][p.y].push_back(p);
    }

    int t = 0;
    while(true){
        if(t > 1000) {t = -1; break;}
        for(int th = 0; th < m;){
            for(int i = 0; i < n; i++){
                for(int j = 0; j < n; j++){
                    for(int k = 0; k < pieces[i][j].size(); k++){
                        piece p = pieces[i][j][k];
                        if(p.th == th){
                            pair<int, int> nx = {p.x + dx[p.dir], p.y + dy[p.dir]}; // 이동하려는 칸
                            th++; // 이동시키려는 말 번호 증가

                            if((nx.x < 0 || nx.y <0 || nx.x >= n || nx.y >= n) || board[nx.x][nx.y] == 2){    // 다음 칸이 파란색이거나 체스판을 벗어나는 경우
                                if(pieces[i][j][k].dir % 2 == 0) pieces[i][j][k].dir++; // 방향 바꿈
                                else pieces[i][j][k].dir--;

                                nx = {p.x + dx[pieces[i][j][k].dir], p.y + dy[pieces[i][j][k].dir]};    // 방향 바꾼 후, 다음 칸

                                // 이동하려는 칸이 파란색이거나, 체스판을 벗어나는 경우 이동하지 않는다.
                                if(nx.x < 0 || nx.y <0 || nx.x >= n || nx.y >= n || board[nx.x][nx.y] == 2) continue; 
                                int s = pieces[nx.x][nx.y].size();
                                move(pieces, {i, j}, nx, k); // 다음 칸에 th번째 말과 그 위에 있는 말들을 옮김
                                
                                if(board[nx.x][nx.y] == 1)  // 다음 칸이 빨간색인 경우
                                    reverse(pieces[nx.x][nx.y].begin() + s, pieces[nx.x][nx.y].end()); // 위에 있던 말의 순서를 바꿈
                            }else if(board[nx.x][nx.y] == 0 || board[nx.x][nx.y] == 1){ // 다음 칸이 흰색 또는 빨간색인 경우
                                int s = pieces[nx.x][nx.y].size();
                                move(pieces, {i, j}, nx, k);    // 다음 칸에 th번째 말과 그 위에 있는 말들을 옮김
                                
                                if(board[nx.x][nx.y] == 1)  // 다음 칸이 빨간색인 경우
                                    reverse(pieces[nx.x][nx.y].begin() + s, pieces[nx.x][nx.y].end()); // 위에 있던 말의 순서를 바꿈
                            }
                            if(pieces[nx.x][nx.y].size() >= 4) {cout << ++t; return 0;} // 말이 4개 이상 쌓이는 순간 게임 종료
                        }
                    }
                }
            }
        }
        
        t++;
    }
    cout << t;
}

 

아래는 말의 움직임을 확인하기 위해 사용된 테스트케이스입니다.

4 4
0 0 2 0
0 0 1 0
0 0 1 2
0 2 0 0
2 1 1
3 2 3
2 2 1
4 1 2

2 2
0 0
0 0
1 1 1
1 2 1

3 3
0 0 0
0 0 0
0 0 0
1 1 1
1 1 1
1 2 1

3 3
1 1 1
1 1 1
1 1 1
1 1 1
1 1 1
1 2 1

4 3
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
1 1 1
1 2 1
1 3 1

4 3
1 1 1 1 
1 1 1 1 
1 1 1 1 
1 1 1 1 
1 1 1
1 2 1
1 3 1