[BOJ] 17780 : 새로운 게임

문제 링크

17780번: 새로운 게임 (acmicpc.net)

17780번: 새로운 게임

재현이가 체스판으로 만든 새로운 게임이 종료되기까지 몇 턴이 걸리는지 출력하는 문제.

요즘 백준 문제집 중에서 danimartinwife 님이 올려주신 ★직접 코테 광탈하면서 모은 문제들☆ 이라는 문제집을 풀어보고 있는데 재밌는 문제들이 많은 것같다.

풀이

규칙을 간단하게 설명하자면

총 K개의 말이 있는데 한 턴에 1번말부터 K번말까지 순서대로 움직인다. 단, 말은 여러개 겹칠 수 있고 만약 말이 겹쳐진 경우 맨 아래에 있는 말만 이동할 수 있다. 이때 위에 쌓여있는 말도 같이 이동한다. 말이 4개 이상 쌓인 칸이 하나라도 있으면 즉시 게임을 종료한다.

여기서 이동할 칸이

1. 흰색이면 그냥 이동한다. 이동하려는 칸에 이미 말이 있으면 이 위에 겹쳐서 쌓는다.

2. 빨간색이면 이동한 후에 쌓여있는 말들을 뒤집는다. 만약 1이 제일 밑에 있고 1,2,3 순으로 쌓여있었다면 3이 제일 아래로 가게되고 3,2,1 순서로 변경된다.

그리고 이미 쌓여져있는 칸에 쌓여진 말을 겹쳐 쌓을때에는 새로 쌓을 말들만 순서를 바꾼다.

3. 파란색 칸이거나 판을 벗어나는 경우 말의 방향을 반대로 바꾸고 한 칸 이동한다. 그 이동할 칸이 만약 또 파란색 칸이거나 판을 벗어난다면 제자리에 가만히있는다.

중요한 것은 말이 여러개 쌓여있을 때 맨 아래에 있는 말만 움직인다는 것이다.

1~K번까지 말을 탐색하면서 맨 아래에 있는 말만 이동시키면 되는 것이다.

for (int i = 1; i <= K; i++) {
			int now_y = Position[i].first;
			int now_x = Position[i].second;
			int horse_num = horse[now_y][now_x][0];
			if (horse_num != i)
				continue;

여기서 horse 는 각 칸에 있는 말의 번호를 저장해둔 벡터이다. 칸에 들어온 순서대로 벡터에 쌓이기 때문에 0번 인덱스에 있는 말이 가장아래에 있는 말을 뜻한다. 따라서 horse_num에는 가장 아래에 있는 말의 번호가 입력되고, 이 번호가 현재 움직일 말의 번호와 같지 않다면 continue로 스킵한다.

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <string.h>
#include <string>
#include <stack>
#include <vector>
#include <math.h>
#include <queue>
#include <climits>
#include <algorithm>
#include <iomanip>
#include <map>
#define mod 998244353
using namespace std;
typedef long long ll;
typedef priority_queue<pair<int, pair<int, int>>, vector<pair<int, pair<int, int>>>, greater<pair<int, pair<int, int>>>> Priority_queue;
const int INF = INT_MAX;
const int MAX_N = 20 + 5;
int N, K;
vector<int> horse[MAX_N][MAX_N];
int Direction[MAX_N];
int Map[MAX_N][MAX_N];
pair<int, int> Position[MAX_N];
int dx[] = { 0,1,-1,0,0 };
int dy[] = { 0,0,0,-1,1 };
 
bool is_ok(pair<int, int> Position) {
    if (Position.first < 1 || Position.first > N || Position.second < 1 || Position.second > N)
        return false;
    return true;
}
 
void Change_Direction(int horse_num) {
    if (Direction[horse_num] == 1) Direction[horse_num] = 2;
    else if (Direction[horse_num] == 2) Direction[horse_num] = 1;
    else if (Direction[horse_num] == 3) Direction[horse_num] = 4;
    else if (Direction[horse_num] == 4) Direction[horse_num] = 3;
}
 
bool Move(pair<int,int> from, pair<int,int> to, int color) {
    if (color == 0) { //흰색
        for (int i = 0; i < horse[from.first][from.second].size(); i++) {
            horse[to.first][to.second].push_back(horse[from.first][from.second][i]);
            Position[horse[from.first][from.second][i]] = { to.first, to.second };
        }
    }
    else if (color == 1) {
        for (int i = (int)horse[from.first][from.second].size() - 1; i >= 0; i--) {
            horse[to.first][to.second].push_back(horse[from.first][from.second][i]);
            Position[horse[from.first][from.second][i]] = { to.first, to.second };
        }
    }
    horse[from.first][from.second].clear();
    if (horse[to.first][to.second].size() >= 4)
        return false;
    return true;
}
 
int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> N >> K;
 
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++)
            cin >> Map[i][j];
    }
 
    for (int i = 1; i <= K; i++) {
        int X, Y, D;
        cin >> Y >> X >> D;
        horse[Y][X].push_back(i);
        Position[i] = { Y,X };
        Direction[i] = D;
    }
    int turn = 0;
    while (true) {
        turn++;
        if (turn > 1000)
            break;
        bool chk = true;
        for (int i = 1; i <= K; i++) {
            int now_y = Position[i].first;
            int now_x = Position[i].second;
            int horse_num = horse[now_y][now_x][0];
            if (horse_num != i)
                continue;
            pair<int, int> next = { now_y + dy[Direction[horse_num]], now_x + dx[Direction[horse_num]] };
            if (!is_ok(next) || Map[next.first][next.second] == 2) {
                Change_Direction(horse_num);
                next = { now_y + dy[Direction[horse_num]],now_x + dx[Direction[horse_num]] };
                if (!is_ok(next) || Map[next.first][next.second] == 2)
                    continue;
                else if (!Move({ now_y,now_x }, next, Map[next.first][next.second])) {
                    chk = false;
                    break;
                }
            }
            else {
                if (!Move({ now_y,now_x }, next, Map[next.first][next.second])) {
                    chk = false;
                    break;
                }
            }
        }
        if (!chk)
            break;
    }
    if (turn > 1000)
        cout << "-1\n";
    else cout << turn << "\n";
    return 0;
}