17780-새로운 게임

www.acmicpc.net/problem/17780

17780번: 새로운 게임

본 문제는 구현 및 시뮬레이션 문제입니다. 푸는데 2일 가량 걸렸을 정도로 저에게는 너무 어려운 문제였습니다.

 

제가 어려웠던점은 말을 쌓아야할때, 연결 관계를 코드로 구현해야하는 점이 어려웠습니다. 처음에는, 말이 쌓이며, 경우에따라 순서도 바뀌어야하니 데이터의 삽입과 Reverse 가 쉽게 가능한 자료구조를 생각해보았습니다. 좀 더 생각해보니 말이 얼마나 혹은 어떻게 쌓이든 바닥에 놓인 말과 가장 높이 놓인 말만 최신화를 잘해준다면 문제를 풀 수 있겠다는 생각이 들었습니다.

 

이를 구현함에있어 먼저 말에 대한 정보인 위치(x, y), 이동 방향(dir), 바닥에 놓여있는지 아닌지를 기록하기 위한 플래그를 구조체화 하였습니다. 그리고 체스판에 대해 각 좌표별로 칸의 색상, 바닥에 놓인 말, 가장 높이 놓인 말, 놓인 말의 갯수를 저장할 수 있도록 [Row][Column][4] 형태의 3차원 배열을 정의하였습니다. 그리고, 차례마다 바닥에 놓인 말들만 규칙에 맞게 이동해가며 말에 대한 정보와 체스판의 정보를 업데이트하고 한 칸위에 말이 4마리 이상 놓였을 때의 차례를 출력하였습니다.

 

좀 더 자세히 설명하면, 말이 이동할때 총 7 가지 경우를 고려해주었습니다. 각 경우에 맞게 말(들)의 위치를 업데이트하고 바닥에 놓이는 말과 가장 위에 놓이는 말, 놓인 말의 갯수를 업데이트 시켜주었습니다.

 

1. 말(들)이 이동하는 칸이 체스판을 벗어나는 경우

2. 말(들)이 이동하는 칸이 파란색 칸인 경우

3. 1. 과 2. 의 경우에 반대 방향으로 이동하였을때 다시 1. 과 2.의 경우에 해당되는 경우

4. 말(들)이 이동하는 칸이 흰색 칸이면서 이동하는 칸에 말(들)이 없는 경우

5. 말(들)이 이동하는 칸이 흰색 칸이면서 이동하는 칸에 말(들)이 있는 경우

6. 말(들)이 이동하는 칸이 빨간색 칸이면서 이동하는 칸에 말(들)이 없는 경우

7. 말(들)이 이동하는 칸이 빨간색 칸이면서 이동하는 칸에 말(들)이 있는 경우

 

저 같은 경우 체스판에 말에 대한 정보를 기록하다보니, 말(들)을 움직이고나서 출발칸과 도착칸에 대한 정보를 갱신해야하고 또 말에 대한 정보도 갱신해주어야 했는데 이과정에서 꼬이면서 많은 시간을 소요하였습니다. 또한, 문제를 잘못읽어 말(들)이 존재하는 빨간 칸에 말(들)을 이동시키는 경우 먼저 쌓아주고 전체를 다시 뒤집는 줄 알았는데, 계속 틀리다가 문제를 다시 읽어보니 기존에 존재하는 말(들)은 가만히 두고, 새롭게 쌓이는 말만 뒤집어 줬어야 했습니다... 난독으로 인해 3시간 가량을 소요하였습니다.

 

코드

#include <iostream>
#include <vector>

using namespace std;

struct Horse
{
    int x; //열
    int y; //행
    int dir; //이동 방향 {1, 2, 3, 4} = {우, 좌, 상, 하}
    bool is_bottom;
};

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

int N;
int K;

int map[13][13][4];
enum{COLOR, BOTTOM, TOP, HORSE_NUMBER};
// 행과 열이 1부터 계산됨 
// [..., COLOR] = map 색상
// [..., BOTTOM] = 몇 번 말이 가장 아래에 놓인지 나타냄, 칸에 말이 없는 경우 -1
// [..., TOP] = 몇 번 말이 가장 위에 놓인지 나타냄, 칸에 말이 없는 경우 -1
// [..., HORSE_NUMBER] = 몇마리의 말이 해당 칸에 놓인지 나타냄

Horse horses[11];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    // freopen("17780.txt", "r", stdin);
    
    cin >> N >> K;

    for(int i = 1; i <= N; i++)
        for(int j = 1; j <= N; j++)
        {
            cin >> map[i][j][COLOR];
            map[i][j][BOTTOM] = -1;
            map[i][j][TOP] = -1;
            map[i][j][HORSE_NUMBER] = 0;
        }

    for(int i = 1; i <= K; i++)
    {
        cin >> horses[i].y >> horses[i].x >> horses[i].dir;
        horses[i].is_bottom = true;
        map[horses[i].y][horses[i].x][BOTTOM] = i;
        map[horses[i].y][horses[i].x][TOP] = i;
        map[horses[i].y][horses[i].x][HORSE_NUMBER] = 1;
    }

    int turn = 0;
    bool mission_complete = false;

    do
    {  
        //simulation
        for(int i = 1; i <= K; i++)
        {
            if(horses[i].is_bottom == false) continue;

            int dir = horses[i].dir;
            int next_x = horses[i].x + dx[horses[i].dir];
            int next_y = horses[i].y + dy[horses[i].dir];

            if(next_x < 1 or next_x > N or next_y < 1 || next_y > N || map[next_y][next_x][COLOR] == 2)
            {
                if(horses[i].dir == 1) horses[i].dir = 2;
                else if(horses[i].dir == 2) horses[i].dir = 1;
                else if(horses[i].dir == 3) horses[i].dir = 4;
                else if(horses[i].dir == 4) horses[i].dir = 3;

                next_x = horses[i].x + dx[horses[i].dir];
                next_y = horses[i].y + dy[horses[i].dir];

                if(next_x < 1 || next_x > N || next_y < 1 || next_y > N || map[next_y][next_x][COLOR] == 2) continue;
            }

            if(map[next_y][next_x][COLOR] == 0) //흰칸
            {
                if(map[next_y][next_x][HORSE_NUMBER] == 0)
                {
                    map[next_y][next_x][BOTTOM] = map[horses[i].y][horses[i].x][BOTTOM];
                    map[horses[i].y][horses[i].x][BOTTOM] = -1;

                    map[next_y][next_x][TOP] = map[horses[i].y][horses[i].x][TOP];
                    map[horses[i].y][horses[i].x][TOP] = -1;

                    map[next_y][next_x][HORSE_NUMBER] = map[horses[i].y][horses[i].x][HORSE_NUMBER];
                    map[horses[i].y][horses[i].x][HORSE_NUMBER] = 0;

                    horses[i].x = next_x;
                    horses[i].y = next_y;
                }
                else //그 위치에 말이 이미 있다면
                {
                    map[horses[i].y][horses[i].x][BOTTOM] = -1;

                    map[next_y][next_x][TOP] = map[horses[i].y][horses[i].x][TOP];
                    map[horses[i].y][horses[i].x][TOP] = -1;
                    
                    map[next_y][next_x][HORSE_NUMBER] += map[horses[i].y][horses[i].x][HORSE_NUMBER];
                    map[horses[i].y][horses[i].x][HORSE_NUMBER] = 0;

                    horses[i].x = next_x;
                    horses[i].y = next_y;
                    horses[i].is_bottom = false;
                }
            }
            else if(map[next_y][next_x][COLOR] == 1) //빨간색 칸
            {
                // 쌓고 순서 반전, bottom 이랑 top 이 swap
                if(map[next_y][next_x][HORSE_NUMBER] == 0)
                {
                    horses[i].is_bottom = false;

                    map[next_y][next_x][TOP] = map[horses[i].y][horses[i].x][BOTTOM];
                    map[horses[i].y][horses[i].x][BOTTOM] = -1;

                    map[next_y][next_x][BOTTOM] = map[horses[i].y][horses[i].x][TOP];
                    map[horses[i].y][horses[i].x][TOP] = -1;

                    map[next_y][next_x][HORSE_NUMBER] = map[horses[i].y][horses[i].x][HORSE_NUMBER];
                    map[horses[i].y][horses[i].x][HORSE_NUMBER] = 0;
                    
                    horses[map[next_y][next_x][BOTTOM]].is_bottom = true;
                    horses[map[next_y][next_x][BOTTOM]].x = next_x;
                    horses[map[next_y][next_x][BOTTOM]].y = next_y;
                }
                else //A, D, F, G가 이동하고, 이동하려는 칸에 말이 E, C, B로 있는 경우에는 E, C, B, G, F, D, A가 된다. 
                {
                    horses[i].is_bottom = false;

                    map[next_y][next_x][TOP] = map[horses[i].y][horses[i].x][BOTTOM];

                    map[horses[i].y][horses[i].x][BOTTOM] = -1;
                    map[horses[i].y][horses[i].x][TOP] = -1;
                    
                    map[next_y][next_x][HORSE_NUMBER] += map[horses[i].y][horses[i].x][HORSE_NUMBER];
                    map[horses[i].y][horses[i].x][HORSE_NUMBER] = 0;
                }
            }

            if(map[next_y][next_x][HORSE_NUMBER] >= 4) 
            {
                mission_complete = true;
                break;
            }
        }
        turn += 1;
    } while (turn <= 1000 and mission_complete == false);
    
    if(turn > 1000) cout << -1;
    else cout << turn;

    return 0;
}