[백준] 17880번 새로운 게임 (C++)

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

 

 

이 문제는 N X N 격자판이 주어지고 말이 1, K번까지 존재하며 말을 순서대로 방향이 적힌대로 움직여야 한다.

이때 움직이려는 방향의 색에 따라서 움직임이 달라진다

 

1. 흰색 칸인 경우 말이 그대로 움직인다 해당칸에 말이 존재하는 경우 움직이려는 말이 위로 올라간다.

2. 말이 이동할때 위에 올려져 있는 말도 함께 이동하며 가장 아래에 있는 말만 이동할 수 있다.

3. 말이 움직이려는 칸이 빨간색인 경우 이동한 후에 위에 쌓여 있는 말의 순서를 바꾼다.

4. 이동하려는 칸이 파란색인 경우 이동방향을 반대로 하고 한 칸 이동한다. 체스판 밖으로 나가는 것도 파란색을 마주한 것과 같은 것으로 간주한다.

 

이러한 조건을 처리하여 말이 4개 이상 쌓인 경우 그 반복하는 횟수를 출력하는 문제이다.

 

N과 M의 범위도 작고 말의 개수도 10개로 굉장히 작다 즉 문제를 똑같이 구현하면 되는 시뮬레이션, 구현 문제이다.

 

 

정답코드

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
#define endl "\n"
#define MAX 1e9

struct coordinate {
    int x;
    int y;
    int r;
};

struct horse {
    int x;
    int y;
    int dir;
};

// int dx[] = {-1, 1, 0, 0, 1, -1, -1, 1};
// int dy[] = {0, 0, -1, 1, -1, 1, -1, 1};
int dx[] = {0, 0, 0, -1, 1};
int dy[] = {0, 1, -1, 0, 0};
int N, K;
int graph[14][14];
vector<int> lst[14][14];
horse ware[14];

void Print() {
    for(int i = 0; i <= N+1; i++) {
        for(int j = 0; j <= N+1; j++) {
            cout << graph[i][j] << " ";
        }
        cout << endl;
    }
}

int changeDir(int dir) {
    if(dir == 1) return 2;
    if(dir == 2) return 1;
    if(dir == 3) return 4;
    if(dir == 4) return 3;

    return 0;
}


void solve() {
    int cnt = 0;

    while(true) {
        cnt++;

        if(cnt > 1000) {
            cout << -1;
            return;
        }
        for(int k = 1; k <= K; k++) {
            int x = ware[k].x;
            int y = ware[k].y;
            int dirs = ware[k].dir;

            if(lst[x][y].front() != k) continue;

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

            if(graph[nx][ny] == 2) {
                dirs = changeDir(dirs);

                nx += dx[dirs] * 2;
                ny += dy[dirs] * 2;
                ware[k].dir = dirs;

                if(graph[nx][ny] == 2) continue;
            }

            if(graph[nx][ny] == 0) {            // 다음 이동할 칸이 흰색인 경우
                for(int l = 0; l < lst[x][y].size(); l++) {
                    ware[lst[x][y][l]].x = nx;
                    ware[lst[x][y][l]].y = ny;

                    lst[nx][ny].push_back(lst[x][y][l]);
                }

                lst[x][y].clear();
            }
            else if(graph[nx][ny] == 1) {
                reverse(lst[x][y].begin(), lst[x][y].end());

                for(int l = 0; l < lst[x][y].size(); l++) {
                    ware[lst[x][y][l]].x = nx;
                    ware[lst[x][y][l]].y = ny;

                    lst[nx][ny].push_back(lst[x][y][l]);
                }

                lst[x][y].clear();
            }
            if(lst[nx][ny].size() >= 4) {
                cout << cnt;
                return;
            }
        }
    }
}

void Init() {
    for(int i = 0; i <= N+1; i++) {
        for(int j = 0; j <= N+1; j++) {
            graph[i][j] = 2;
        }
    }
}

void input() {
    cin >> N >> K;

    Init();

    for(int i = 1; i <= N; i++) {
        for(int j = 1; j <= N; j++) {
            cin >> graph[i][j];
        }
    }

    for(int i = 1; i <= K; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        ware[i].x = a;
        ware[i].y = b;
        ware[i].dir = c;

        lst[a][b].push_back(i);
    }
}

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

    input();
    solve();
}

 

정답코드를 하나씩 뜯어보자

 

말을 관리하는 구조체

struct horse {
    int x;
    int y;
    int dir;
};

 

말의 위치와 어디로 이동해야할지 관리하기 위해 horse라는 구조체를 만들어 K개의 말을 담았다.

 

사용할 변수

int graph[14][14];
vector<int> lst[14][14];
horse ware[14];

그래프와 말을 쌓기 위한 2차원 배열을 리스트로 할당하였다. 이때 바깥으로 나가는 경우 파란색벽과 마주하기 때문에

미리 그래프를 모두 2(파란색)으로 초기화 시켜주었고 입력을 받았다.

 

방향전환

int changeDir(int dir) {
    if(dir == 1) return 2;
    if(dir == 2) return 1;
    if(dir == 3) return 4;
    if(dir == 4) return 3;

    return 0;
}

 

만약 이동하려는 칸이 파란색인 경우 이동방향을 반대로 해야하기 때문에 방향을 바꾸는 함수를 따로 만들어주었다.

 

메인 부분

void solve() {
    int cnt = 0;

    while(true) {
        cnt++;

        if(cnt > 1000) {
            cout << -1;
            return;
        }
        for(int k = 1; k <= K; k++) {
            int x = ware[k].x;
            int y = ware[k].y;
            int dirs = ware[k].dir;

            if(lst[x][y].front() != k) continue;

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

            if(graph[nx][ny] == 2) {
                dirs = changeDir(dirs);

                nx += dx[dirs] * 2;
                ny += dy[dirs] * 2;
                ware[k].dir = dirs;

                if(graph[nx][ny] == 2) continue;
            }

            if(graph[nx][ny] == 0) {            // 다음 이동할 칸이 흰색인 경우
                for(int l = 0; l < lst[x][y].size(); l++) {
                    ware[lst[x][y][l]].x = nx;
                    ware[lst[x][y][l]].y = ny;

                    lst[nx][ny].push_back(lst[x][y][l]);
                }

                lst[x][y].clear();
            }
            else if(graph[nx][ny] == 1) {
                reverse(lst[x][y].begin(), lst[x][y].end());

                for(int l = 0; l < lst[x][y].size(); l++) {
                    ware[lst[x][y][l]].x = nx;
                    ware[lst[x][y][l]].y = ny;

                    lst[nx][ny].push_back(lst[x][y][l]);
                }

                lst[x][y].clear();
            }
            if(lst[nx][ny].size() >= 4) {
                cout << cnt;
                return;
            }
        }
    }
}

 

말이 K만큼 있고 말의 순서대로 반복해야 하기 때문에 for문을 사용하였고 만약 말이 맨 아래에 위치하지 않았다면 이는 말이 올라갔다는 말이며 말이 움직일때는 아래에 있는 말이 움직여야하기 때문에 건너 뛰었다. 

 

이후 만약 다음칸이 파란색 칸인 경우 반대방향으로 움직여야 하기 때문에 nx, ny가 파란색 칸이며 반대방향으로 2칸을 이동해야 하므로 

X2를 하여 두칸을 건너 뛰었다. 또한 그 반대 칸도 파란색 칸인 경우 continue로 건너 뛰어줬으며

 

흰색 칸인 경우 다음칸의 배열에 순차적으로 넣어주었으며 이전칸은 clear 함수를 사용하여 없애 주었다.

 

마지막으로 빨간색 칸인 경우 이는 뒤집어야하기 때문에 reverse 함수를 사용하였고 이전칸은 clear 함수를 사용하여 없애주었다.

 

 

회고록

사실 문제 읽는데만 거의 20분을 사용한 문제이다. 또한 빨간색 칸을 만났을때 위로 올리고 뒤집어야하는줄 알았는데 뒤집고 넣어줘야 해서 이것때문에 계속 답이 안나와 골치아팠다 문제를 제대로 읽자....