ABOUT ME

IT에 관한 다양한 정보를 공유하는 블로그입니다.

Today
Yesterday
Total
  • #17837 새로운 게임 2
    Code/BOJ 2020. 2. 9. 20:01
    728x90
    반응형

    출처: https://www.acmicpc.net/problem/17837

     

    17837번: 새로운 게임 2

    재현이는 주변을 살펴보던 중 체스판과 말을 이용해서 새로운 게임을 만들기로 했다. 새로운 게임은 크기가 N×N인 체스판에서 진행되고, 사용하는 말의 개수는 K개이다. 말은 원판모양이고, 하나의 말 위에 다른 말을 올릴 수 있다. 체스판의 각 칸은 흰색, 빨간색, 파란색 중 하나로 색칠되어있다. 게임은 체스판 위에 말 K개를 놓고 시작한다. 말은 1번부터 K번까지 번호가 매겨져 있고, 이동 방향도 미리 정해져 있다. 이동 방향은 위, 아래, 왼쪽, 오른쪽

    www.acmicpc.net

    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번 말의 이동 방향을 반대로 하고 한 칸 이동한다. 방향을 반대로 한 후에 이동하려는 칸이 파란색인 경우에는 이동하지 않고 방향만 반대로 바꾼다.
    • 체스판을 벗어나는 경우에는 파란색과 같은 경우이다.

    실수했던 부분은 파란색을 밟고 그 다음 위치가 원래위치일 경우 그 자리가 빨간색일때 순서를 바꿔주면 안되는데 바꿔 계속 틀렸다. 문제 설명이 조금 부족한 감이 없지 않아 있다.

     

    소스코드

    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번 말의 이동 방향을 반대로 하고 한 칸 이동한다. 방향을 반대로 한 후에 이동하려는 칸이 파란색인 경우에는 이동하지 않고 방향만 반대로 바꾼다.
    • 체스판을 벗어나는 경우에는 파란색과 같은 경우이다.
    // #17837 새로운 게임 2
    #include <iostream>
    #include <deque>
    #include <cstring>
    #include <algorithm>
    using namespace std;
    int dir[5][2] = { {0,0}, { 0,1 }, { 0,-1 }, { -1,0 }, { 1,0 } };
    int map[13][13];//0은 흰,1은 빨,2는 파
    int n, k;// 맵 사이즈, 말의 수
    typedef struct info {
    int num;//드론 넘버
    int x, y, d;
    };
    typedef struct info2 {
    int num, d;
    };
    info init_dron[11];
    deque <info2> dron[13][13];
    void move_dron(int dron_num,int x,int y,int nx,int ny,int nd,int keep_idx,int dron_size,int red) {
    //cout << "x " << x << " y " << y << " nx " << nx << " ny " << ny << " nd " << nd <<" keepidx "<<keep_idx<<" red "<<red<< endl;
    if (x == nx && y == ny) {
    init_dron[dron_num].d = nd;
    dron[nx][ny][keep_idx].d = nd;
    return;
    }
    init_dron[dron_num] = { dron_num,nx,ny,nd };
    dron[x][y][keep_idx] = { dron_num,nd };
    if (red==0) {
    for (int i = keep_idx; i < dron_size; i++) {
    int num = dron[x][y][i].num, d = dron[x][y][i].d;
    init_dron[num].x = nx, init_dron[num].y = ny;
    dron[nx][ny].push_back({ num,d });
    }
    for (int i = keep_idx; i < dron_size; i++) {
    dron[x][y].pop_back();
    }
    }
    else if(red==1) {
    for (int i = dron_size-1; i >= keep_idx; i--) {
    int num = dron[x][y][i].num, d = dron[x][y][i].d;
    //cout << "red stack num " << num << endl;
    dron[x][y].pop_back();
    init_dron[num].x = nx, init_dron[num].y = ny;
    dron[nx][ny].push_back({ num,d });
    }
    }
    //cout << endl;
    }
    int simul() {
    //맨 처음 드론 넣기
    for (int i = 1; i <= k; i++) {
    int x = init_dron[i].x, y = init_dron[i].y, num = init_dron[i].num, d = init_dron[i].d;
    dron[x][y].push_back({ num,d });
    }
    int TIME = 1;
    while (TIME <= 1000) {
    for (int dron_num = 1; dron_num <= k; dron_num++) {
    int x = init_dron[dron_num].x, y = init_dron[dron_num].y, d = init_dron[dron_num].d;
    if (dron[x][y].size() >= 4)return TIME;
    int keep_idx;//해당 인덱스부터 마지막까지 데리고 다님
    int dron_size = dron[x][y].size();
    int nx = x + dir[d][0], ny = y + dir[d][1], nd = d;
    for (int i = 0; i < dron_size; i++) {
    if (dron[x][y][i].num == dron_num) {
    keep_idx = i;
    break;
    }
    }
    //파란색인 경우
    if (nx <= 0 || ny <= 0 || nx > n || ny > n || map[nx][ny] == 2) {
    if (nd % 2 == 0) {
    if (nd == 2)nd = 1;
    else nd = 3;
    }
    else nd += 1;
    nx = x + dir[nd][0], ny = y + dir[nd][1];
    if (nx <= 0 || ny <= 0 || nx > n || ny > n || map[nx][ny] == 2) {
    nx = x, ny = y;
    }
    }
    //흰색인 경우
    if (map[nx][ny] == 0) {
    move_dron(dron_num,x, y, nx, ny, nd, keep_idx, dron_size,0);
    }
    //빨간색인 경우
    else if (map[nx][ny] == 1) {
    move_dron(dron_num,x, y, nx, ny, nd, keep_idx, dron_size, 1);
    }
    if (dron[nx][ny].size() >= 4)return TIME;
    }
    TIME++;
    }
    return -1;
    }
    void Input() {
    cin >> n >> k;
    for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
    cin >> map[i][j];
    }
    }
    int x, y, d;
    for (int i = 1; i <= k; i++) {
    cin >> x >> y >> d;
    init_dron[i] = { i,x,y,d };
    }
    }
    int main() {
    Input();
    cout << simul() << endl;
    }
    728x90
    반응형

    'Code > BOJ' 카테고리의 다른 글

    순열, 조합 뽑기 연습 N과 M (1)~(12)  (0) 2020.02.09
    #17135 캐슬 디펜스  (0) 2020.02.09
    #14500 테트로미노  (0) 2020.01.05
    #17406 배열 돌리기 4  (0) 2020.01.05
    #2718 타일 채우기  (0) 2020.01.05
Designed by Tistory.