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

www.acmicpc.net/problem/17780

17780번: 새로운 게임

 

 

 

알고리즘 종류

구현

 

 

 

사고 과정

1. 말의 상태를 담을 수 있는 배열이 필요할 것 같았습니다. 그래서 Piece라는 구조체를 만들고, 이 구조체로 ps라는 배열을 만들었습니다. 구조체에는 말의 위치(y, x)와 방향(d) 그리고 맨 밑인지(isButtom)를 확인하는 변수들이 있습니다.

 

2. 말을 쌓을 수 있어야 합니다. 그래서 3차원 벡터를 만들기로 했습니다. state라는 명을 붙였습니다.

 

3. 이제 턴 1회당 밑에 있는 말만 확인하여 옮깁니다. 옮길 때 흰색 / 붉은색 / 파란색인지에 따라 동작을 다르게 합니다.

 

 

구현(C++)

#include <iostream>
#include <vector>
#include <algorithm>
 
using namespace std;
 
struct Piece{
    int y;
    int x;
    int d;
    bool isBottom;
    
};
 
int n, k;
 
int mat[15][15];
vector<int> state[15][15];
Piece ps[15];
int dir[5][2] = {{0,0}, {0,1}, {0,-1}, {-1,0}, {1,0}};
 
 
bool isValid(int y, int x){
    return (y>=1 && y<=n) && (x>=1 && x<=n);
}
 
// 흰색으로 이동  
void go_white(int cy, int cx, int ny, int nx){
    
    if(state[ny][nx].size() != 0) ps[state[cy][cx][0]].isBottom = false;
    
    for(int i=0; i<state[cy][cx].size(); i++){
        state[ny][nx].push_back(state[cy][cx][i]);
        int num = state[cy][cx][i];
        ps[num].y = ny;
        ps[num].x = nx;
    }
    state[cy][cx].clear();
}
 
// 붉은색으로 이동  
void go_red(int cy, int cx, int ny, int nx){
    
    ps[state[cy][cx][0]].isBottom = false;
    reverse(state[cy][cx].begin(), state[cy][cx].end());
    
    for(int i=0; i<state[cy][cx].size(); i++){
        state[ny][nx].push_back(state[cy][cx][i]);
        int num = state[cy][cx][i];
        ps[num].y = ny;
        ps[num].x = nx;
    }
    
    state[cy][cx].clear();
    for(int i=1; i<state[ny][nx].size(); i++) ps[state[ny][nx][i]].isBottom = false;
    
    ps[state[ny][nx][0]].isBottom = true;
}
 
// 파란색으로 이동  
void go_blue(int cy, int cx, int cd){
    
    int nd;
    if(cd==1) nd=2;
    else if(cd==2) nd=1;
    else if(cd==3) nd=4;
    else if(cd==4) nd=3;
    
    ps[state[cy][cx][0]].d = nd;
    
    int ny = cy + dir[nd][0];
    int nx = cx + dir[nd][1];
    
    if(isValid(ny, nx)){
        if(mat[ny][nx] == 0) go_white(cy, cx, ny, nx);
        else if(mat[ny][nx] == 1) go_red(cy, cx, ny, nx);
    }
}
 
// 4개 이상이 쌓였는지 확인  
bool check(){
    for(int i=1; i<=n; i++){
        for(int j=1; j<=n; j++){
            if(state[i][j].size() >= 4) return true;
        }
    }
    return false;
}
 
 
void solution(){
    
    int ans = 0;
    while(true){
        
        if(check()){
            cout << ans << endl;
            return;
        }
        if(ans > 1000){
            cout << -1 << endl;
            return;
        }
        
        for(int i=1; i<=k; i++){
            if(!ps[i].isBottom) continue;
            
            int cy = ps[i].y;
            int cx = ps[i].x;
            int cd = ps[i].d;
            
            int ny = cy + dir[cd][0];
            int nx = cx + dir[cd][1];
            
            if(mat[ny][nx]==2 || !isValid(ny, nx)) go_blue(cy, cx, cd);
            else if(mat[ny][nx]==0) go_white(cy, cx, ny, nx);
            else if(mat[ny][nx]==1) go_red(cy, cx, ny, nx);
        }
        
        ans ++;
    }
}
 
 
int main(void){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    cin >> n >> k;
    
    for(int i=1; i<=n; i++){
        for(int j=1; j<=n; j++){
            cin >> mat[i][j];
        }
    }
    
    int a,b,c;
    for(int i=1; i<=k; i++){
        cin >> a >> b >> c;
        ps[i] = {a, b, c, true};
        state[a][b].push_back(i);
    }
    
    solution();
}

 

 

 

시행착오