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

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

[ 문제 바로가기 ]

[ 문제풀이 ]

1) 새로운게임(17780) 과 매우 유사하지만, 조금 더 복잡해진 문제이다.

   새로운게임을 풀고 오지 않으신 분들은 먼저 풀어보고 오길 권장하겠습니다 !

   이 글의 설명 또한 전체적인 로직이 새로운게임과 비슷하고, 비교를 하면서 작성되었으니 풀어보고 오시는걸

   권장드립니다.

   [ 새로운게임(17780) 문제 바로가기 ]

   [ 새로운게임(17780) 문제풀이 바로가기 ]

  

   새로운게임 에서 말을 옮길 때, 가장 밑에 있는 말이 아니라면 움직일 수 없었지만 이 문제에서는 현재 움직이려는

   말과 그 위에 올라가 있는 말들을 움직여 줄 수 있다. 즉, 가장 밑에 존재하는 말이 아니더라도 움직일 수 있다.

 

   먼저, 전체적인 로직은 새로운게임 에서 말했던 풀이와 비슷하다.

   이 문제에서도 맵의 상태를 관리하는 2차원배열 벡터를 똑같이 사용할 것이다.

   기존의 로직에서 추가된 부분에 대해서만 알아보자.

   이 문제에서 말을 옮기기 위해서는 "현재 말이 위치하고 있는 곳" 을 알아야한다. 여기서 말하는 "위치하는 곳"  이라는 것은

   맵에서의 좌표 값을 의미하는 것이 아닌, 그 좌표에 존재하는 말들 중에서 현재 말이 위치하고 있는 곳을 의미한다.

   간단한 예시를 보면서 알아보자.

  

    먼저 파랑색 칸을 보자. 파랑색 칸에서 'B'는 몇 번째 위치하고 있는 놈일까 ?? 바로 0번째이다.

    노랑색 칸에서 'B'는 ? 1번에 위치 하고 있다.

    초록색칸에서 'B'는 ? 2번에 위치하고 있다.

    이렇게 움직이려는 말이 해당 좌표에서 몇 번째에 위치하고 있는지(가장 아래로 부터) 알아야 한다.

    그럼 이걸 어떻게 알아내야 할까 ??

    우리는 처음에 "맵의 상태를 관리하는 2차원배열 벡터"를 사용한다고 했다.

    그럼 노랑색 칸을 기준으로 보자. 노랑색 칸의 좌표인 (2, 2)에는 'C', 'B', 'A'가 순서대로 push되어 있을 것이다.

    그럼, (2, 2)에서 단순 for문을 통해서 'B'를 쉽게 찾아낼 수 있다. 이 때, 'B'를 몇 번만에 찾았는지를 가져오기만 하면 된다.

    즉, 코드로 나타내면 다음과 같이 쓸 수있다.

  for (int i = 0; i < MAP_State[x][y].size(); i++)

  {
      if (MAP_State[x][y][i] == Idx) return i;   

     // Idx = 현재 찾고자 하는 말
  }

    

    위의 과정을 통해서 몇 번째에 위치하는지 찾아냈다면 이제 실제로 색깔별로 옮기는 과정을 알아보자.

    '새로운게임' 문제 풀이를 제 글로 읽으신 분들은 아시겠지만, 본인은 움직이는 과정을 함수로 이용해서 구현하였다.

    이 때, 매개변수가 조금 많아져서 매개변수에 대한 설명부터 하겠다.

    총 7개의 매개변수를 사용했다.

    현재 x좌표, 현재 y좌표, 움직일 x좌표, 움직일 y좌표, 움직이려는 말의 번호,

    말이 어디에 위치하는지(위에서 구한 값), 움직이려는 칸의 색깔

    이렇게 총 7개의 매개변수를 호출해 주었다.

     지금부터, (x, y) = 현재좌표 , (nx, ny) = 움직이려는 좌표, Pos = 말이 어디에 위치하는지(위에서 구한 값) 으로 표현

     해 보겠다.

     1. (nx, ny) = 0 일 때

     - 단순하게 움직여 주기만 하면 된다. 물론, 움직이려는 말의 현재 위치보다 더 높이 있는 말들은 함께 움직여 줘야 한다.

       실제 코드로 빗대어 설명하자면, (x, y)에 있는 말들 중에서, 현재 움직이려는 말부터 그 위에 있는 말들만 (nx, ny)에

       push_back() 연산을 해주고, (x, y)에서 pop_back() 연산을 해줘야 한다는 것이다.

       이걸 어떻게 ?? 그래서 우리가 'Pos'를 구해놓은 것이다.

       (x, y)에서 'Pos' 부터 (x, y)의 size() 까지 (nx, ny)에 push_back()을 해주면 된다.

       위에서 봤던 노랑색 칸 그림을 다시한번 봐보자. 저 그림에서, (x, y)의 크기 = 3이고, B의 Pos 값은 1일 것이다.

       즉, 1번부터 ~ 2번까지만 (nx, ny)에 push_back()을 해준다면, 마치, 'B'번 말부터 그 위에 있는 말들만

       옮기는 효과가 있게 된다.

       그럼 이렇게 해서 옮겼다고 쳐보자. 그럼 삭제하는건 ? (x, y)에서 옮긴만큼만 맵에서 삭제해줘야 한다.

       이 부분을 위해서 본인은 "해당 말이, 해당 좌표에서 역순으로 몇번째에 위치하는지" 를 찾아주었다.

       초록색 칸을 예시로 생각해보자.

       나는 지금 초록색 칸에서 'C'를 움직일 것이다.(그림상, C가 아랫방향으로 움직인다고 되어있지만, 방향은 일단

       생각하지 않고 움직인다고 가정하겠습니다.)

       그럼 위에서 말한 방법대로 'C'가 있는 Pos값인 '1'을 계산한 후에, 1번째, 2번째, 3번째 말들을 옮겨서

       (nx , ny)에 3개의 말을 옮겼다고 가정해보자. 그리고 나서 삭제하기 위해서 역순으로 몇번째 존재하는지

       찾는 것이다. 'C'는 역순으로 3번에 존재한다.

       "역순이라고 하면, 가장 위에 있는 말이 0번이 되기 때문에 'C'는 2번이 되는거 아니야?" 라고 생각할 수 있는데

       이 경우에는 위치가 아니라, 갯수를 체크해주기 위함이다.

       결과부터 말하자면, 이 갯수만큼 pop_back() 즉, 삭제하는 연산을 할 것이다.

       'C'가 역순으로 세번째에 존재하기 때문에, pop_back() 연산을 3번만 한다면 ??

       'C','B','A'가 초록색 칸에서 pop_back() 되어 사라질 것이다.

       옮기는 과정과 삭제하는 연산을 합쳐보면 마치, 'C','B','A'가 (nx, ny)에 옮겨지고, 'C','B','A',가 (x, y)에서

       사라지는 것과 같은 효과를 볼 수가 있다.

  

     2. (nx, ny) = 1 일 때

      - 전체적인 로직은 (nx, ny) = 0 일 때와 비슷하지만, 순서를 바꿔줘야 한다는 문제가 있다.

        기존의 문제인 새로운게임 에서는 전체 순서를 바꾼 다음에, 옮겨주면 그만이었지만, 이 경우에는 전체 순서를

        바꾸면 안되기 때문에 본인은 역순으로 (nx, ny)에 push_back() 연산을 해주었다.

        (nx, ny) = 0일 때는 Pos ~ 해당 좌표의 크기를 순차적으로 push해주었는데, 이 경우에는 반대로 해주는 것이다.

        초록색 칸으로 가보자. 'C'를 움직이려고 하는데, 움직이려는 칸이 빨강색 칸이다 !

        그럼, 해당 좌표의 크기 - 1 ~ Pos 까지 역으로 (nx, ny)에 push해주는 것이다.

        그렇게 되면 당연히 (nx, ny)에는 역순으로 들어간 것 처럼 보이게 된다.

        삭제하는 과정은 (nx, ny) = 0 일 때와 동일하다.

     3. (nx, ny) = 2 or (nx, ny)가 맵의 범위가 아닌 경우

      - 이 경우는 기존 풀이법과 동일하다.

      본인은 위의 방식대로 문제를 풀었는데, 계속 틀렸습니다가 떴었다.

      그래서 한참을 헤맸었는데, 본인이 문제를 잘못 이해한건지, 문제가 애매한 부분이 있는건지는 모르겠는데

      말이 '4개 이상이 쌓이게 되는 최초 턴의 수'를 출력하는 것 이라고 해놔서, 모든 말이 움직이는게 한 턴이라고

      생각했는데, 말을 움직이다가 중간과정에서 4개 이상이 쌓이게 되면 종료하게 만들었더니 pass를 받을 수 있었다.

      쉽게 말해서 5개의 말이 있는데, 5개의 말을 움직이고 상태를 확인하고, 5개의 말을 움직이고 상태를 확인하고,

      이런 방법으로 했더니 답이 나오질 않았는데, 1번말 움직이고 상태확인하고, 2번말 움직이고 상태확인하고, 3번말

      움직이고 상태확인하고... 를 반복했더니 pass를 받을 수 있었다.

      이 부분 주의하자 !

[ 소스코드 ]

#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;
};
 
int N, K, Answer;
int MAP[MAX][MAX];
vector<int> MAP_State[MAX][MAX];
CHESS Chess[CHESS_MAX];
 
int dx[] = { 0, 0, 0, -1, 1 };
int dy[] = { 0, 1, -1, 0, 0 };
 
void Print()
{
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            cout << MAP_State[i][j].size() << " ";
        }
        cout << endl;
    }
    cout << "#######################################################################" << endl;
}
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 };
        MAP_State[x][y].push_back(i);
    }
}
 
int Find_Delete_Num(int x, int y, int Chess_Num)
{
    /* 해당 말을 옮긴 후, 기존 좌표에서 몇 번 삭제를 해야 하는지 찾는 함수. */
    int Cnt = 0;
    for (int i = MAP_State[x][y].size() - 1; i >= 0; i--)
    {
        if (MAP_State[x][y][i] == Chess_Num) break;
        Cnt++;
    }
    return Cnt + 1;
}
 
int Reverse_Dir(int Num)
{
    int Dir = Chess[Num].dir;
    if (Dir == 1) return 2;
    else if (Dir == 2) return 1;
    else if (Dir == 3) return 4;
    else if (Dir == 4) return 3;
}
 
void MoveChess(int x, int y, int nx, int ny, int Chess_Num, int Pos, int Ms)
{
    if (Ms == 0)
    {
        for (int i = Pos; 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;
        }
        int Delete_Num = Find_Delete_Num(x, y, Chess_Num);
        for (int i = 0; i < Delete_Num; i++) MAP_State[x][y].pop_back();
    }
    else if (Ms == 1)
    {
        for (int i = MAP_State[x][y].size() - 1; i >= Pos; 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;
        }
        int Delete_Num = Find_Delete_Num(x, y, Chess_Num);
        for (int i = 0; i < Delete_Num; i++) MAP_State[x][y].pop_back();
    }
    else if (Ms == 2)
    {
        int Dir = Reverse_Dir(Chess_Num);
        Chess[Chess_Num].dir = Dir;
        int nnx = x + dx[Dir];
        int nny = y + dy[Dir];
        
        if (nnx >= 0 && nny >= 0 && nnx < N && nny < N)
        {
            if (MAP[nnx][nny] != 2) MoveChess(x, y, nnx, nny, Chess_Num, Pos, MAP[nnx][nny]);
        }
    }
}
 
int Find_Position(int x, int y, int Idx)
{
    /* 해당 말이 몇 번째에 위치하고 있는지 찾아서 return 하는 함수. */
    for (int i = 0; i < MAP_State[x][y].size(); i++)
    {
        if (MAP_State[x][y][i] == Idx) return i;
    }
}
 
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 Time = 0;
    while (1)
    {
        if (Time > 1000) break;
 
        for (int i = 0; i < K; i++)
        {
            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];
 
            int Pos = Find_Position(x, y, i);
            if (nx >= 0 && ny >= 0 && nx < N && ny < N) MoveChess(x, y, nx, ny, i, Pos, MAP[nx][ny]);            
            else MoveChess(x, y, nx, ny, i, Pos, 2);
 
            if (Check_State() == true)
            {
                Flag = true;
                break;
            }
        }
        if (Flag == true) break;
        Time++;
    }
 
    if (Flag == true) cout << Time + 1 << 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;
}