[백준/BOJ] 17780번 - 새로운 게임[C++]

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

17780번: 새로운 게임

 

안녕하세요 오랜만에 포스팅 남깁니다.

이번 문제는 해결방법을 떠올리는 것은 쉽지만 구현이 많고 복잡한 부분이 있기에 Gold 2라는 난이도가 책정된 것 같습니다.

한번 보시죠!

 

1. 문제

재현이는 주변을 살펴보던 중 체스판과 말을 이용해서 새로운 게임을 만들기로 했다. 새로운 게임은 크기가 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번 말의 이동 방향을 반대로 하고 한 칸 이동한다. 방향을 반대로 한 후에 이동하려는 칸이 파란색인 경우에는 이동하지 않고 방향만 반대로 바꾼다.
  • 체스판을 벗어나는 경우에는 파란색과 같은 경우이다.

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

 

문제가 그림과 봐야 좋을 듯 하니 링크에서 보시는 걸 추천드립니다^^

 

2. 풀이

풀이는 간단합니다.

체스판의 최대 크기가 12 x 12, 체스말의 최대 개수가 10, 반복횟수가 최대 1000번 이기 때문에 시간복잡도를 고려하지 않고 구현을 해주면 되겠습니다.

 

한 턴을 쓸 때마다 모든 체스말을 체크해주어야 하며 그 중에서도 해당 체스말이 가장 아래에 존재할 때만 이동이 가능합니다.

제가 고려한 순서는 이러한데요.1. 이동할 칸이 blue거나 체스판 밖이라면 방향 전환 후 다음 이동할 칸이 어디인지 체크 후 또 다시 blue거나 체스판 밖이라면 다음 체스말 차례로(고려할 필요가 없다면 2, 3번으로)2. 이동할 칸이 white라면 이동3. 이동할 칸이 red라면 역순으로 재정렬 후 이동4. 이동 완료 후 해당 칸의 높이가 4이상인지 확인

 

3. 코드

코드가 좀 길지만 함수별로 어떤 동작을 하는지 보시면 조금은 편하실 겁니다. 너저분한 코드라 죄송합니다..

//https://www.acmicpc.net/problem/17780
//17780. 새로운 게임(Gold 2, 구현)

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;

int N, K, ans = 0;
int direction[11]; //체스말의 이동방향
pair<int, int> p[11]; //체스말의 위치
int color[13][13]; //체스칸의 색깔
int height[13][13]; //체스칸의 말의 높이
int sq_arr[13][13][11]; //해당 체스칸의 체스말 배열
//idx순서대로 1은 우향, 2는 좌향, 3은 북향, 4는 남향
int dx[5] = {0, 0, 0, -1, 1};
int dy[5] = {0, 1, -1, 0, 0};
int a_flag = 0; //a_flag는 높이가 4 이상인게 생겼는지 체크,

void reverse(int x, int y) {
    if(height[x][y] <= 1) return;
    for(int i = 0; i < height[x][y] / 2; i++) {
        int tmp = sq_arr[x][y][i];
        sq_arr[x][y][i] = sq_arr[x][y][height[x][y] - 1 - i];
        sq_arr[x][y][height[x][y] - 1 - i] = tmp;
    }
}

void white(int x, int y, int nx, int ny) {
    for(int i = height[nx][ny]; i < height[nx][ny] + height[x][y]; i++) {
        //복사
        sq_arr[nx][ny][i] = sq_arr[x][y][i - height[nx][ny]];
    }
    //체스말 위치 변경 + 원래 칸 초기화 
    for(int i = 0; i < height[x][y]; i++) {
        p[sq_arr[x][y][i]].first = nx;
        p[sq_arr[x][y][i]].second = ny;
        sq_arr[x][y][i] = 0;
    }
    height[nx][ny] += height[x][y];
    height[x][y] = 0;
    if(height[nx][ny] >= 4) a_flag = 1;
}

void red(int x, int y, int nx, int ny) {
    //순서를 뒤집은 후에 그대로 옮겨주면 되므로, 본인 칸에서 순서 뒤집기 -> white()
    reverse(x, y);
    white(x, y, nx, ny);
}

void blue(int k) {
    if(direction[k] == 1) direction[k] = 2;
    else if(direction[k] == 2) direction[k] = 1;
    else if(direction[k] == 3) direction[k] = 4;
    else if(direction[k] == 4) direction[k] = 3;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    freopen("input.txt", "r", stdin);

    //INPUT
    memset(height, 0, sizeof(height));
    memset(sq_arr, 0, sizeof(sq_arr));
    cin >> N >> K;
    for(int i = 1; i <= N; i++) {
        for(int j = 1; j <= N; j++) {
            cin >> color[i][j];
        }
    }
    //체스말의 위치와 방향 입력 후 체스칸에도 반영해주기
    for(int i = 1; i <= K; i++) {
        int tx, ty;
        cin >> tx >> ty >> direction[i];
        p[i].first = tx, p[i].second = ty;
        sq_arr[tx][ty][0] = i;
        height[tx][ty] = 1;
    }

    //SOLVE
    while(true) {
        ans++;
        //모든 말을 한번씩
        for(int i = 1; i <= K; i++) {
            int x = p[i].first;
            int y = p[i].second;
            //만약 현재 움직여야할 체스말이 가장 아래에 있는 것이 아니라면 skip
            if(sq_arr[x][y][0] != i) continue;

            int nx = x + dx[direction[i]];
            int ny = y + dy[direction[i]];

            //갈 곳이 blue 혹은 체스판 밖이라면
            if(nx < 1 || nx > N || ny < 1 || ny > N || color[nx][ny] == 2) {
                //방향 바꿔주기
                blue(i);
                nx = x + dx[direction[i]];
                ny = y + dy[direction[i]];
                //blue 바꿔준 후에도 blue가 나온 것이기 때문에 그냥 넘겨준다.
                if(nx < 1 || nx > N || ny < 1 || ny > N || color[nx][ny] == 2) {
                    continue;
                }
            }

            //갈 곳이 white라면
            if(color[nx][ny] == 0) {
                white(x, y, nx, ny);
            }
            //갈 곳이 red라면
            else if(color[nx][ny] == 1) {
                red(x, y, nx, ny);
            }

            if(a_flag) break;
        }
        //4이상이면 종료
        if(a_flag || ans > 1000) break;
    }

    //OUTPUT
    if(ans > 1000) ans = -1;
    cout << ans;
}

 

이런 문제는 디버깅이 오래 걸리는데 테케를 몇개를 해봐도 다 맞게 나와서 2시간이나 걸린 문제였네요.

white 함수에서 이동할 칸의 높이가 0인 경우를 괜히 구분했다가 오류잡는 데 힘들었습니다 하하

오랜만에 입꼬리가 내려갈 뻔했지만 읽으시는 분들 스마일한 하루 되시고

struct, vector를 사용하면 더 깔끔한 코드가 될 듯 하니 도전해보세용~@!