[백준] 17837. 새로운 게임2

[문제]

www.acmicpc.net/problem/17837

17837번: 새로운 게임 2

[풀이]

시뮬레이션 문제로 문제 조건 잘 지켜가면서 풀었다.

 

하나의 turn 마다 1번 말부터 순서대로 움직인다.

한 칸에 여러 말이 쌓여 있을 수 있고 이동하려는 말 위에 다른 말이 존재한다면 같이 움직인다.

한 칸에 말이 4마리 이상 쌓일 경우 게임이 종료된다.

 

 

이동하려는 칸이 흰색인 경우 이동하려는 말의 위에 있는 말부터 쌓이기 시작한다.

이동하려는 칸이 빨간색일 경우 이동하려는 말부터 쌓이기 시작한다.

이동하려는 칸이 파란색일 경우 반대 방향으로 바꾸고 움직인다.

방향을 바꿔도 파란색이라면 움직이지 않는다.

범위를 벗어나는 경우도 파란색의 경우와 동일하게 한다.

 

---

solve 함수에서 1번 말부터 움직이고

이동하려는 칸의 색깔에 알맞게 white, red, blue에 맞는 함수를 호출했다.

blue인 경우 방향을 바꾸고 움직여야 하므로 동일하게 move 함수를 호출한다.

red , white의 경우 말이 움직이는 순서만 다를 뿐 다른 것은 같으므로

move 함수 하나로 처리하고 말이 쌓일 때만 white인지 red 인지 구분하여 쌓이는 순서를 다르게 해줬다.

 

 

[코드]

 

시간 : 0ms

 

#include <iostream>
#include <vector>

#define MAX 12

using namespace std;

int N,K;
int color[MAX][MAX]={0,};
vector<int> map[MAX][MAX];

int dx[4] = {0,0,-1,1};
int dy[4] = {1,-1,0,0};

struct HORSE{
    int x,y,dir;
};
HORSE horse[10];

bool move(int col , int idx)
{
    int x = horse[idx].x;
    int y = horse[idx].y;
    int dir = horse[idx].dir;
    
    int nx = x+dx[dir];
    int ny = y+dy[dir];
    
    
    vector<int> v;
    int _size = map[x][y].size();
    
    while(1)
    {
        int num = map[x][y][_size-1];
        _size--;
        map[x][y].pop_back();
        v.push_back(num);
        if(num==idx)    break;
    }
    
    if(col ==0){
        for(int i=v.size()-1;i>=0;i--)
        {
            int num = v[i];
            map[nx][ny].push_back(num);
            horse[num].x= nx;
            horse[num].y = ny;
        }
    }
    else {

        for(int i=0;i<v.size();i++)
        {
            int num = v[i];
            map[nx][ny].push_back(num);
            horse[num].x= nx;
            horse[num].y = ny;
        }
    }
    
    if(map[nx][ny].size() >= 4) return false;
    return true;
}


bool blue(int idx)
{
    bool res = true;
    
    int x = horse[idx].x;
    int y = horse[idx].y;
    int dir = horse[idx].dir;
    
    int nx = x+dx[dir];
    int ny = y+dy[dir];

    if(nx< 0 ||  ny < 0  || nx >= N || ny >= N || color[nx][ny]==2)   return true;
    else if(color[nx][ny]==0)  res = move(0,idx);
    else if(color[nx][ny]==1) res = move(1,idx);
    
    return res;
    
}

bool solve()
{
    
    for(int i=0;i<K;i++){
        bool res=true;
        int x = horse[i].x;
        int y = horse[i].y;
        int dir = horse[i].dir;
        
        int nx = x+dx[dir];
        int ny = y+dy[dir];
        
        if(nx< 0 ||  ny < 0  || nx >= N || ny >= N || color[nx][ny]==2){
            
            if(dir ==0) horse[i].dir=1;
            else if(dir ==1) horse[i].dir=0;
            else if(dir ==2) horse[i].dir=3;
            else if(dir ==3) horse[i].dir=2;
            res = blue(i);
        }
        else if(color[nx][ny]==0)  res = move(0,i);
        else if(color[nx][ny]==1) res = move(1,i);
        
        if(res==false)  return false;
    }
    return true;
}
    
int main(void)
{
    scanf("%d %d",&N,&K);
    
    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++){
            scanf("%d",&color[i][j]);
        }
    }
    
    for(int i=0;i<K;i++){
        int x,y,dir;
        scanf("%d %d %d",&x,&y,&dir);
        horse[i] = {x-1,y-1,dir-1};
        map[x-1][y-1].push_back(i);
    }
    
    int turn=0;
    
    while(1){
        turn++;
        if(!solve())    break;
        else if(turn > 1000){
            printf("-1");
            return 0;
        }
    }
    printf("%d",turn);

    return 0;
    
}