[백준] 17780 새로운 게임

17780번: 새로운 게임

 

www.acmicpc.net

풀이

체스판을 배열로 구현하고, 각 칸을 vector를 사용하여 맨 아래에 있는 말부터 차례로 쌓이도록 구현하여 해결하였다.

코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

struct Knight {
    int x, y, dir;
    bool canMove;
}k[11];

int N, K;
int map[13][13];
vector<int> list[13][13];
const int dx[] = { 0, 1, -1, 0, 0 }, dy[] = { 0, 0, 0, -1, 1 }, back[] = { 0, 2, 1, 4, 3 };

int moveKnight(int idx) {
    int nx = k[idx].x + dx[k[idx].dir];
    int ny = k[idx].y + dy[k[idx].dir];

    // 체스판을 벗어나거나 파란색 칸으로 간 경우
    if (nx < 1 || nx > N || ny < 1 || ny > N || map[ny][nx] == 2) {
        k[idx].dir = back[k[idx].dir];
        nx = k[idx].x + dx[k[idx].dir];
        ny = k[idx].y + dy[k[idx].dir];

        if (nx < 1 || nx > N || ny < 1 || ny > N || map[ny][nx] == 2) return list[k[idx].y][k[idx].x].size();
    }
    // 현재 위치에 있는 말들을 저장한 배열
    vector<int>& cur = list[k[idx].y][k[idx].x];
    // 옮길 위치에 있는 말들을 저장한 배열
    vector<int>& next = list[ny][nx];

    // 빨간색 칸으로 간 경우
    if (map[ny][nx] == 1) reverse(cur.begin(), cur.end());

    // 현재 위치에 있는 말을 다음 위치로 모두 이동
    // 다음 위치에 기존의 말들이 있을 수 있으므로 canMove를 false로 설정
    for (auto it = cur.begin(); it != cur.end(); it++) {
        k[*it].x = nx;
        k[*it].y = ny;
        k[*it].canMove = false;
        next.push_back(*it);
    }
    // 옮기기 전과 옮긴 후의 말의 수가 같으면 next.size()가 원래는 0이었다는 의미이므로 맨 아래 말을 움직일 수 있도록 변경
    if (next.size() == cur.size()) k[next[0]].canMove = true;
    // 기존의 말이 있던 칸 초기화
    cur.clear();
    return next.size();
}

int simulation() {
    for (int i = 1; i <= 1000; i++) {
        for (int j = 1; j <= K; j++) {
            // 말이 움직일 수 없는 경우
            if (k[j].canMove == false) continue;
            int cnt = moveKnight(j);
            if (cnt >= 4) return i;
        }
    }
    return -1;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    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++) {
        cin >> k[i].y >> k[i].x >> k[i].dir;
        k[i].canMove = true;
        list[k[i].y][k[i].x].push_back(i);
    }
    cout << simulation() << '\n';
    return 0;
}