[ 백준 17780 ] 새로운 게임 (C++)

백준의 새로운 게임(17780) 문제이다.

[ 문제 바로가기 ]

[ 문제풀이 ]

1) 문제에서 제시한 조건에 맞게 말을 움직여 주면 되는 문제이다.

   먼저 본인이 사용한 변수들에 대해서 부터 알아보자.

   1. 말의 상태를 관리하는 구조체 배열

   - 본인은 구조체 하나를 사용해서 말을 관리해 주었다. 구조체의 멤버변수로는 { x좌표 , y 좌표 , 진행방향 , 가장아래 }

     4개를 사용해 주었다. x좌표 y좌표는 말 그대로 현재 말이 있는 좌표이고, 진행방향 또한 말 그대로이다.

     가장 마지막 변수는 "현재 말이 가장 아래에 있는지" 를 판단해주는 bool형 변수이다.

     말이 여러개가 쌓여 있을 경우, 현재 움직이려는 말이 가장 아래에 있지 않다면, 그 말은 움직일 수가 없기 때문이다.

     당연히 초기에는 쌓여있는 말이 존재하지 않기 때문에 저 변수의 값은 모두 true이다.

   2. 맵의 상태를 관리하는 2차원 배열 형태의 벡터

   - 입력받을 맵을 저장하는 변수 int MAP[MAX][MAX] 이외에도 하나의 맵을 더만들어 주었다.

     바로, vector<int> MAP_State[MAX][MAX] 이다. 이 벡터에는 현재 좌표에 들어있는 맵의 상태를 나타낸다.

     예를들어서 MAP_State[0][0] = { 1, 2, } 라고 되어있다면, 이는 현재 (0, 0)에 1번말과 2번말이 있습니다 를

     의미한다. 가장 앞에 있는(0번째 Index) 가 가장 아래있는 놈으로 판단해 주었다.

2) 이제 말을 움직여보자. 지금부터 말을 간단하게 (x, y)에서 (nx, ny)로 움직인다고 가정해보자.

   1. (nx, ny)가 0 인 Case.

   - 0일 경우에는 말을 정말 그대로 움직여 주기만 하면 된다. 단 ! 이미 (nx, ny)에 또 다른 말이 존재할 경우

     말이 쌓이게 된다. 즉, (x, y)에서는 현재의 말이 가장 아래 위치한 말이였을 수 있지만, (nx, ny)에 또 다른 말이

     존재할 경우, 가장 아래에 위치하지 않는다.

   2. (nx, ny)가 1 인 Case.

   - 1일 경우에는, (x, y)에서 말을 뒤집어서 (nx, ny)로 움직여 주었다.

     (nx, ny)로 옮긴 후에 뒤집으면 안되나 ?? 그래도 상관은 없다. 단 주의해야 할 점은 기존에 (nx, ny)에 또 다른

    말이 존재한다면, 그 말들은 뒤집히지 않는다는 것이다.

    예를 들어서 (x, y) = {A , B, C } 이고, (nx, ny) = { D , E } 일 때, (x, y)에 있는 말들을 (nx,ny)로 옮기게 되면

    (nx, ny) = { D, E, C, B, A } 가 되지, (nx, ny) = { A, B, C, E, D } 가 되는 것이 아니다 !

    즉, (nx, ny)로 옮긴 후에 뒤집든, (x, y)에서 뒤집어서 옮기든 상관은 없지만 위에서 말한 경우를 조심해서 구현해

    주어야 한다.

   3. (nx, ny)가 2 인 Case.

   - 2일 경우에는, 진행 방향을 바꿔주고 움직여 주기만 하면 된다. 단 ! 진행 방향을 바꾼 후에 움직일 경우에

     해당 맵이 '2' 이거나 맵의 범위 밖이면 진행 방향만 바꿔주고 멈춰버리면 된다.

   4. (nx, ny)가 맵의 범위 가 아닌 Case.

   - 3번 Case와 똑같다. 진행 방향을 바꿔주고 움직여 주되, 진행 방향을 바꾼 후에 해당 맵이 '2'이거나

    맵의 범위 밖이면 진행 방향만 바꿔주고 멈춰버리면 된다.

[ 소스코드 ]

#include<iostream>
#include<vector>
 
#define endl "\n"
#define MAX 12
#define CHESS_MAX 10
using namespace std;
 
struct CHESS        // 말을 관리하는 구조체
{
    int x;
    int y;
    int dir;
    bool Under;
};
 
int N, K;
int MAP[MAX][MAX];
int dx[] = { 0, 0, 0, -1, 1 };
int dy[] = { 0, 1, -1, 0, 0 };
CHESS Chess[CHESS_MAX];
vector<int> MAP_State[MAX][MAX];    // 맵의 상태를 나타내는 벡터 2차원 배열.
 
void Input()
{
    cin >> N >> K;
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            cin >> MAP[i][j];
        }
    }
    for (int i = 0; i < K; i++)
    {
        int x, y, d; cin >> x >> y >> d;
        x--; y--;
        Chess[i] = { x, y, d, true };
        MAP_State[x][y].push_back(i);
    }
}
 
void Reverse_Chess(int x, int y)
{
    /* 
    (x , y)에 존재하는 말의 순서를 뒤집는 함수 
    - 'Temp' 라는 임시 벡터에 (x, y)에 있는 모든 말들을 옮겨주고 
      거꾸로 (x, y)에 넣어주었다.
    - 가장 아래에 위치한 말이 달라지니 Check.
    */
    vector<int> Temp;
    for (int i = 0; i < MAP_State[x][y].size(); i++) Temp.push_back(MAP_State[x][y][i]);
    MAP_State[x][y].clear();
    for (int i = Temp.size() - 1; i >= 0; i--)
    {
        MAP_State[x][y].push_back(Temp[i]);
        Chess[Temp[i]].Under = false;
    }
    Chess[MAP_State[x][y][0]].Under = true;
}
 
int Reverse_Dir(int d)
{
    /* 방향 전환 함수 */
    if (d == 1) return 2;
    else if (d == 2) return 1;
    else if (d == 3) return 4;
    else if (d == 4) return 3;
}
 
void Change_State(int x, int y, int nx, int ny, int Ms)
{
    /* 실제로 말을 움직이는 함수 */
    if (Ms == 0)    // 1번 Case. (nx, ny) = 0
    {
        if (MAP_State[nx][ny].size() != 0) Chess[MAP_State[x][y][0]].Under = false;    
        for (int j = 0; j < MAP_State[x][y].size(); j++)
        {
            MAP_State[nx][ny].push_back(MAP_State[x][y][j]);
            int Idx = MAP_State[x][y][j];
            Chess[Idx].x = nx;
            Chess[Idx].y = ny;
        }
        MAP_State[x][y].clear();
    }
    else if (Ms == 1)    // 2번 Case. (nx, ny) = 1
    {
        Reverse_Chess(x, y);
        for (int i = 0; i < MAP_State[x][y].size(); i++)
        {
            MAP_State[nx][ny].push_back(MAP_State[x][y][i]);
            int Idx = MAP_State[x][y][i];
            Chess[Idx].x = nx;
            Chess[Idx].y = ny;
        }
        MAP_State[x][y].clear();
        for (int i = 1; i < MAP_State[nx][ny].size(); i++)
        {
            Chess[MAP_State[nx][ny][i]].Under = false;
        }
    }
    else if (Ms == 2)    // 3번 Case. (nx, ny) = 2
    {
        int Dir = Reverse_Dir(Chess[MAP_State[x][y][0]].dir);
        Chess[MAP_State[x][y][0]].dir = Dir;
        int nnx = Chess[MAP_State[x][y][0]].x + dx[Dir];
        int nny = Chess[MAP_State[x][y][0]].y + dy[Dir];
 
        if (nnx >= 0 && nny >= 0 && nnx < N && nny < N)
        {
            if (MAP[nnx][nny] != 2) Change_State(x, y, nnx, nny, MAP[nnx][nny]);
        }
    }
}
 
bool Check_State()
{
    for(int i = 0 ; i < K; i++)
    { 
        int x = Chess[i].x;
        int y = Chess[i].y;
        
        if (MAP_State[x][y].size() >= 4) return true;
    }
    return false;
}
 
void Solution()
{
    bool Flag = false;
    int Cnt = 0;
    while (1)
    {
        if (Check_State() == true)
        {
            Flag = true;
            break;
        }
        if (Cnt > 1000) break;
 
        for (int i = 0; i < K; i++)
        {
            if (Chess[i].Under == false) continue;
            int x = Chess[i].x;
            int y = Chess[i].y;
            int Dir = Chess[i].dir;
 
            int nx = x + dx[Dir];
            int ny = y + dy[Dir];
            if (nx >= 0 && ny >= 0 && nx < N && ny < N) Change_State(x, y, nx, ny, MAP[nx][ny]);
            else Change_State(x, y, nx, ny, 2);
        }
        Cnt++;
    }
 
    if (Flag == true) cout << Cnt << endl;
    else cout << -1 << endl;
}
 
void Solve()
{
    Input();
    Solution();
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}