[Algorithm] 백준 17837 - 새로운 게임 2

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

17837번: 새로운 게임 2

문제

재현이는 주변을 살펴보던 중 체스판과 말을 이용해서 새로운 게임을 만들기로 했다. 새로운 게임은 크기가 N×N인 체스판에서 진행되고, 사용하는 말의 개수는 K개이다. 말은 원판모양이고, 하나의 말 위에 다른 말을 올릴 수 있다. 체스판의 각 칸은 흰색, 빨간색, 파란색 중 하나로 색칠되어있다.

게임은 체스판 위에 말 K개를 놓고 시작한다. 말은 1번부터 K번까지 번호가 매겨져 있고, 이동 방향도 미리 정해져 있다. 이동 방향은 위, 아래, 왼쪽, 오른쪽 4가지 중 하나이다.

턴 한 번은 1번 말부터 K번 말까지 순서대로 이동시키는 것이다. 한 말이 이동할 때 위에 올려져 있는 말도 함께 이동한다. 말의 이동 방향에 있는 칸에 따라서 말의 이동이 다르며 아래와 같다. 턴이 진행되던 중에 말이 4개 이상 쌓이는 순간 게임이 종료된다.

• A번 말이 이동하려는 칸이
  • 흰색인 경우에는 그 칸으로 이동한다. 이동하려는 칸에 말이 이미 있는 경우에는 가장 위에 A번 말을 올려놓는다.
    • A번 말의 위에 다른 말이 있는 경우에는 A번 말과 위에 있는 모든 말이 이동한다.
    • 예를 들어, A, B, C로 쌓여있고, 이동하려는 칸에 D, E가 있는 경우에는 A번 말이 이동한 후에는 D, E, A, B, C가 된다.
  • 빨간색인 경우에는 이동한 후에 A번 말과 그 위에 있는 모든 말의 쌓여있는 순서를 반대로 바꾼다.
    • A, B, C가 이동하고, 이동하려는 칸에 말이 없는 경우에는 C, B, A가 된다.
    • A, D, F, G가 이동하고, 이동하려는 칸에 말이 E, C, B로 있는 경우에는 E, C, B, G, F, D, A가 된다.
  • 파란색인 경우에는 A번 말의 이동 방향을 반대로 하고 한 칸 이동한다. 방향을 반대로 바꾼 후에 이동하려는 칸이 파란색인 경우에는 이동하지 않고 가만히 있는다.
  • 체스판을 벗어나는 경우에는 파란색과 같은 경우이다.

다음은 크기가 4×4인 체스판 위에 말이 4개 있는 경우이다.

첫 번째 턴은 다음과 같이 진행된다.

두 번째 턴은 다음과 같이 진행된다.

체스판의 크기와 말의 위치, 이동 방향이 모두 주어졌을 때, 게임이 종료되는 턴의 번호를 구해보자.

생각해 보기

덱을 사용하여 m에는 현재 위치에 말의 idx를 순서대로 넣고 말의 위치와 이동정보는 wh에서 가져온다.

덱 m에 위치와 이동정보까지 넣게 되는 경우 지속적으로 읽고 쓰는 횟수가 증가할 것이라 생각해 분할하여 저장 하였다. 

 

 

1. 하얀색으로 움직이는 경우
   • dq의 순행으로 다음 이동 m에 넣어준다.

 

1. 빨간색으로 움직이는 경우
   • dq의 역순으로 다음 이동 m에 넣어준다.

 

1. 파란색으로 움직이는 경우, 체스판을 벗어나는 경우

          파란색으로 움직이는 경우 우선 이동방향을 바꿔야 하므로 me(이동방향)을 우선 바꿔준다.

          그 다음 다음 이동경로 ny와 nx를 계산하고 다음 칸의 색을 체크해준다.

 

1. 1. 파란색으로 움직이는 경우, 체스판을 벗어나는 경우 - 여기서 틀렸었다.
      • 이동방향은 변경하지 않은 채로 ny와 nx를 다음 위치가 아닌 현재 위치의 m에 순행으로 넣어준다.
   2. 하얀색으로 움직이는 경우
      • dq의 순행으로 다음 이동 m에 넣어준다.
   3. 빨간색으로 움직이는 경우
      • dq의 역순으로 다음 이동 m에 넣어준다.

 

코드보기

#include<iostream>
#include<vector>
#include<deque>

using namespace std;

typedef struct Dat{
    int y,x,m;
}dat;

vector<dat> wh;
deque<int> m[15][15];

int color[15][15];
int my[5]={0,0,0,-1,1};
int mx[5]={0,1,-1,0,0};

int N,K;

void mv_white(deque<int> dq, int y, int x){
    while(!dq.empty()){
        int n=dq.front();
        dq.pop_front();

        m[y][x].push_back(n);
        wh[n].y=y;
        wh[n].x=x;
    }
}

void mv_red(deque<int> dq, int y, int x){
    while(!dq.empty()){
        int n=dq.back();
        dq.pop_back();

        m[y][x].push_back(n);
        wh[n].y=y;
        wh[n].x=x;
    }
}

bool mv(){
    for(int i=0;i<K;i++){
        int y=wh[i].y;
        int x=wh[i].x;
        int me=wh[i].m;

        deque<int> dq;
        while(m[y][x].back()!=i){
            dq.push_front(m[y][x].back());
            m[y][x].pop_back();
        }
        m[y][x].pop_back();
        dq.push_front(i);

        int ny=y+my[me];
        int nx=x+mx[me];

        if(ny<1||nx<1||ny>N||nx>N||color[ny][nx]==2){//파랑
            if(me==1)
                me=2;
            else if(me==2)
                me=1;
            else if(me==3)
                me=4;
            else if(me==4)
                me=3;
            ny=y+my[me];
            nx=x+mx[me];
            wh[i].m=me;

            if(ny<1||nx<1||ny>N||nx>N||color[ny][nx]==2){//파랑 -> 파랑
                ny=y;
                nx=x;

                mv_white(dq,ny,nx);
            }
            else if(color[ny][nx]==0){//파랑 -> 하양
                mv_white(dq,ny,nx);
            }
            else if(color[ny][nx]==1){//파랑 -> 빨강
                mv_red(dq,ny,nx);
            }
        }
        else if(color[ny][nx]==0){//하양
            mv_white(dq,ny,nx);
        }
        else if(color[ny][nx]==1){//빨강
            mv_red(dq,ny,nx);
        }
        

        if(m[ny][nx].size()>=4)
            return true;
    }
    return false;
}

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

    int y,x,me;
    cin>>N>>K;
    for(int i=1;i<=N;i++)
        for(int j=1;j<=N;j++)
            cin>>color[i][j];

    for(int i=0;i<K;i++){
        cin>>y>>x>>me; 
        wh.push_back({y,x,me});
        m[y][x].push_back(i);
    }

    int cnt=0;
    while(++cnt<=1000){
        if(mv())
            break;
    }
    
    if(cnt>1000)
        cout<<-1<<'\n';
    else
        cout<<cnt<<'\n';

    return 0;
}

• 구현
• 시뮬레이션