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

새로운 게임 문제 링크 (BOJ 17780번 문제): https://www.acmicpc.net/problem/17780 

17780번: 새로운 게임

문제 풀이

*실수하면 안되는 부분* 

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

 

1. 바깥지점은 파란 지점과 동일하게 인식하므로 바깥 지점을 모두 값 2로 채워줍니다.

2. 각 지점에 말을 놓고, 가장 아래 있는 말만 이동할 수 있도록 하기 위해 (좌표 값, 방향, 맨밑에 있는지)를 저장합니다. 

3. 반복문을 돌면서 맨 밑에 말이 있는 경우에 move() 를 수행해줍니다. 

    3.1. 파란색 지점을 만날 경우, 방향을 반대로 전환 (Convert Direction)

           3.1.1 흰색 지점을 만난 경우

           3.1.2 빨간 지점을 만난 경우

           3.1.3 파란 지점을 만난 경우 (Stop) 

    3.2 흰색 지점을 만난 경우 (Move)

    3.3 빨간 지점을 만난 경우 (Reverse Move) 

 

파란 지점(3.1)을 만났을 때, 반대 방향이 파란 지점(3.1.3)일 경우만 따로 처리해준다면, 결국 파란 지점(3.1)을 만난 이후 흰색 지점 혹은 빨간 지점을 만나게 되어 있으므로 파란 지점(3.1)을 만난 경우를 먼저 처리해줍니다. 

 

각 경우 마다 좌표 옮기기, 말 쌓기를 수행해준다면 해당 문제를 해결할 수 있습니다. 단, 말 쌓기를 진행할 때, 다음 위치에 말이 존재한다면, 현재 위치에 있는 말의 bottom 값을 false로 바꾸고, 다음 위치에 첫 번째 말을 true로 바꿔주는 것이 핵심입니다. 

 

#include <bits/stdc++.h> 
#define SIZE 15
using namespace std ; 

typedef struct horse { 
    int y, x ; 
    int d ; 
    bool bottom ; 
} horse ; 

vector<horse> V ; 
int N, K ; 
int A[SIZE][SIZE] ; // 1: red, 2: blue
vector<int> B[SIZE][SIZE] ;
int dx[4] = {1,-1,0,0} ; 
int dy[4] = {0,0,-1,1} ; 

int convert_direction(int k) { 
    if ( k == 0 ) return 1 ; 
    else if ( k == 1 ) return 0 ; 
    else if ( k == 2 ) return 3 ; 
    else if ( k == 3 ) return 2 ; 
    return -1; 
}

int move(int i) { 
    int ny = V[i].y + dy[V[i].d] ; 
    int nx = V[i].x + dx[V[i].d] ; 

    if ( A[ny][nx] == 2 ) { 
        V[i].d = convert_direction(V[i].d) ; 

        ny = V[i].y + dy[V[i].d] ; 
        nx = V[i].x + dx[V[i].d] ; 

        if ( A[ny][nx] == 2 ) return 0 ; 
    } 

    vector<int> &curr = B[V[i].y][V[i].x] ;
    vector<int> &next = B[ny][nx] ;  

    if ( A[ny][nx] == 0 ) {     
        if ( !next.empty() ) V[curr.front()].bottom = false; 
        next.insert(next.end(), curr.begin(), curr.end()) ; 
    } else if ( A[ny][nx] == 1) { 
        next.insert(next.end(), curr.rbegin(), curr.rend()) ; 
        V[next.back()].bottom = false; 
        V[next.front()].bottom = true;  
    }

    V[next.front()].y = V[next.back()].y = ny ; 
    V[next.front()].x = V[next.back()].x = nx ; 
    curr.clear() ; 
    return next.size() ;
}

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

    cin >> N >> K ;
    for (int i = 0 ; i <= N + 1 ; i++) { 
        for (int j = 0; j <= N + 1; j++) { 
            if ( i == 0 || j == 0 || i == N + 1|| j == N + 1 ) {
                A[i][j] = 2 ;
            } else {
                cin >> A[i][j] ;
            }
        }
    }

    for (int i = 0 ; i < K ; i++) { 
        int x,y,d; cin >> y >> x >> d ; 

        B[y][x].push_back(i) ;
        V.push_back({y, x, d - 1, true}) ; 
    }

    int round ;
    for (int round = 1 ; round <= 1000 ; round++) { 
        for (int i = 0 ; i < K ; i++) { 
            if ( V[i].bottom ) {
                int cnt = move(i) ;  
                if ( cnt >= 4 ) {
                    cout << round << '\n'; 
                    return 0 ;
                } 
            }
        }
    }

    cout << -1 << '\n'; 
    
    return 0 ;
}