[Baekjoon][17837] 새로운 게임 2

출처 - 백준사이트

17837번: 새로운 게임 2

나의 풀이

이 문제는 어렵지는 않으나 구현할때 어떤 형태로 구현할지 생각하는게 중요한 문제인 것 같다.
나는 Map을 만들때, 맵의 색깔과 맵에 쌓여있는 말들을 list 자료구조로 만들어서 구현하였다.

#include <iostream>
#include <vector>
#include <list>

#define MAX_SIZE    12

using namespace std;

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

typedef struct _hores {
    _hores(int x, int y, int dir) : x(x), y(y), dir(dir) {}
    ~_hores() {}

    int x;
    int y;
    int dir;
} Horse;

int N, K, result;
bool isEnd = false;
pair<int,list<Horse*>> map[MAX_SIZE][MAX_SIZE];
vector<Horse> position_horse;

void moving(list<Horse*>::iterator itr, int idx, int ny, int nx) {
    if (0 > ny || ny >= N || 0 > nx || nx >= N || map[ny][nx].first == 2) {
        if (position_horse[idx].dir % 2)
            position_horse[idx].dir = (position_horse[idx].dir - 1) % 4;
        else
            position_horse[idx].dir = (position_horse[idx].dir + 1) % 4;

        int updated_ny = position_horse[idx].y + dy[position_horse[idx].dir];
        int updated_nx = position_horse[idx].x + dx[position_horse[idx].dir];

        if (0 <= updated_ny && updated_ny < N && 0 <= updated_nx && updated_nx < N) {
            if (map[updated_ny][updated_nx].first != 2)
                moving(itr, idx, updated_ny, updated_nx);

            if (map[updated_ny][updated_nx].second.size() >= 4)
                isEnd = true;
        }
    }
    else {
        int ori_y = position_horse[idx].y;
        int ori_x = position_horse[idx].x;

        if (map[ny][nx].first == 0) {
            for (list<Horse*>::iterator move_itr = itr ; move_itr != map[ori_y][ori_x].second.end() ; ) {
                map[ny][nx].second.push_back(*move_itr);
                map[ny][nx].second.back()->y = ny;
                map[ny][nx].second.back()->x = nx;
                move_itr = map[ori_y][ori_x].second.erase(move_itr);
            }
        }
        else if (map[ny][nx].first == 1) {
            list<Horse*>::reverse_iterator move_ritr = map[ori_y][ori_x].second.rbegin();

            while (1) {
                map[ny][nx].second.push_back(*move_ritr);
                map[ny][nx].second.back()->y = ny;
                map[ny][nx].second.back()->x = nx;

                move_ritr++;

                if (map[ny][nx].second.back() == *itr)
                    break;
            }

            for (list<Horse*>::iterator move_itr = itr ; move_itr != map[ori_y][ori_x].second.end() ; )
                move_itr = map[ori_y][ori_x].second.erase(move_itr);
        }

        if (map[ny][nx].second.size() >= 4)
            isEnd = true;
    }
}

void turn() {
    // idx = 말의 순서
    for (int idx = 0 ; idx < position_horse.size() && !isEnd ; idx++) {
        // num은 맵에 있는 deque의 순환 iterator
        for (list<Horse*>::iterator itr = map[position_horse[idx].y][position_horse[idx].x].second.begin() ; itr != map[position_horse[idx].y][position_horse[idx].x].second.end() ; itr++) {
            if (&position_horse[idx] == *itr) { // 현재의 말순서에 해당하는 말과 맵의 deque에 있는 말과 같은경우.
                int ny = position_horse[idx].y + dy[position_horse[idx].dir];
                int nx = position_horse[idx].x + dx[position_horse[idx].dir];

                moving(itr, idx, ny, nx);
                break;
            }
        }
    }
}

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

    cin >> N >> K;

    for (int y = 0 ; y < N ; y++) {
        for (int x = 0 ; x < N ; x++)
            cin >> map[y][x].first;
    }

    for (int i = 0 ; i < K ; i++) {
        int y, x, dir;

        cin >> y >> x >> dir;
        position_horse.push_back(Horse(x - 1, y - 1, dir - 1));
    }

    for (vector<Horse>::iterator itr = position_horse.begin() ; itr != position_horse.end() ; itr++)
        map[itr->y][itr->x].second.push_back(&(*itr));

    while (1) {
        turn();
        result++;

        if (result > 1000) {
            result = -1;
            break;
        }
        else if (isEnd)
            break;
    }

    cout << result;

    return 0;
}