[BOJ] 17837. 새로운 게임 2

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

17837번: 새로운 게임 2

시뮬레이션 문제이다. 어떻게 말의 정보들을 저장하고 말을 이동시킬까 고민하다가 다음과 같이 구현해봤다.

 

 

 

말의 정보는 구조체를 만들어서 행과 열의 위치, 방향을 넣어서 벡터에 저장한다.

벡터의 i번째 위치에는 i번째 말의 위치와 방향이 저장되어 있다.

 

방향 정보는 문제에서 알려준 순서대로 오른쪽, 왼쪽, 위쪽, 아래쪽이 각각 1, 2, 3, 4번의 인덱스가 되도록 배열에 넣어놓는다. 1번부터 시작하기 위해서 0번 위치에는 그냥 0을 넣어놨다.

 

말을 이동시키기 위해서는 deque배열을 사용하였다.

deque<int> dq[13][13];

위와같이 deque<int>를 타입으로 가지는 2차원 배열이다.

dp[x][y]에는 x행 y열 위치에 있는 말들이 순서대로 저장되어 있다.

 

(queue가 아닌 deque를 사용한 이유는 이동할 칸이 빨간색인경우 순서를 반대로 넣어주기 위해서 사용하였다.)

(효율적인 방법인지는 잘모르겠다. 채점현황을 보니 메모리를 더 사용하는 것 같은데 다른 분들 풀이도 찾아봐야겠다...)

 

 

 

이제 턴을 진행하면서 4개 이상이 쌓이는 경우가 있다면 바로 게임을 종료하고 턴 수를 리턴한다.

문제 조건에 따라 1,000보다 크거나 절대로 게임이 종료되지 않는 경우에는 -1을 출력하기 위해서 -1을 리턴한다.

각 턴에서는 1번말부터 k번말까지 순차적으로 이동시킨다.

 

 

 

이동할 칸이

1. 범위를 벗어나거나 파란색 칸인 경우
   • 원래 좌표에서 방향을 반대로 바꾼다.
     1. 다시 한칸을 이동할건데 이동할 칸이 또 범위를 벗어나거나 파란색일 경우 문제 조건에 따라 방향만 바꾼채로 더 이동하지 않는다.
     2. 그렇지 않다면 이동을 한건데 이동할 칸이 흰색이냐 빨간색이냐에 따라 다르게 이동할 것이므로 아래 조건들(밑에 2번, 3번 조건)을 이어서 실행해주면 된다.
2.  흰색인 경우
   • 현재 이동할 말의 번호가 num이라고 했을때
   • 현재 이동할 말의 위에 있는 말들을 함께 이동시켜주기위해서 deque에서 num번 말이 나오는 이후의 말들은 모두 같이 이동시켜주면된다.
   • deque에 들어있는 말들의 개수만큼만 반복문을 진행하면서
     1. num번이 나오지 않았다면 다시 원래 위치 deque에 넣어준다.
     2. num번이 나왔거나 이전에 num번이 나왔다면 이동할 위치의 deque에 넣어준다. (이동할 때는 해당 말의 위치정보(벡터에 넣어놓은 값)을 업데이트 해주어야한다)
3. 빨간색인 경우
   • 현재 이동할 말의 번호가 num이라고 했을때
   • 현재 이동할 말의 위에 있는 말들을 순서를 반대로 이동시켜주기 위해서 deque의 뒷부분부터 num번까지의 말들을 순차적으로 이동시켜준다.
   • deque에 들어있는 말들의 개수만큼만 반복문을 진행하면서 num이 나올때까지 이동할 위치의 deque에 넣어주고 num번이 나온다면 num번말도 이동시켜주고 반복문을 종료한다.

 

 

 

이동을 매번 할때마다 이동한 칸에 쌓인 말이 4개 이상이 되었는지 확인하고

4개 이상이 되었다면 true를 리턴, 그렇지 않다면 false를 리턴한다.

#include <iostream>
#include <vector>
#include <deque>
using namespace std;
 
int n, k;
int map[13][13];
 
//오, 왼, 위, 아래
int dx[] = { 0,0,0,-1,1 };
int dy[] = { 0,1,-1,0,0 };
 
 
deque<int> dq[13][13];
 
struct Horse {
    int x;
    int y;
    int dir;
    Horse(int a, int b, int c) {
        x = a;
        y = b;
        dir = c;
    }
};
 
 
//말의 정보를 저장할 벡터
vector<Horse> vt;
 
 
bool move(int num) {
 
    //num번호 말의 좌표와 방향
    int x = vt[num].x;
    int y = vt[num].y;
    int dir = vt[num].dir;
 
    int nx, ny, tmp;
    
    //이동할 좌표
    nx = x + dx[dir];
    ny = y + dy[dir];
 
 
    //이동할 좌표가 파란색이거나 범위를 벗어나는 경우
    if (nx < 1 || ny < 1 || nx > n || ny > n || map[nx][ny] == 2) {
        //방향 전환
        if (dir == 1 || dir == 3) dir++;
        else dir--;
 
        //반대로 다시 한칸 이동
        nx = x + dx[dir];
        ny = y + dy[dir];
        
 
        //말의 방향정보 업데이트
        vt[num].dir = dir;
 
 
        //다시 이동한 칸이 또 파란색이거나 범위를 벗어나면 방향만 바꾸고 리턴
        if (nx < 1 || ny < 1 || nx > n || ny > n || map[nx][ny] == 2) {
            return false;
        }
 
        //그렇지 않다면 아래남은 코드 진행
    }
    
 
    //이동할 칸이 흰색인 경우
    if (map[nx][ny] == 0) {
        bool flag = false;
 
        int size = dq[x][y].size();
        for (int i = 0; i < size; i++) {
            tmp = dq[x][y].front();
            dq[x][y].pop_front();
 
            if (tmp == num || flag) {
                //num번 말이랑 num위에 있는 말들만 이동한다.
                flag = true; //ture로 바꿔주면 앞으로 뒤에 있는 말들은 같이 이동한다.
 
 
                //이동시켜준다.
                dq[nx][ny].push_back(tmp);
                
                //좌표정보 업데이트
                vt[tmp].x = nx;
                vt[tmp].y = ny;
            }
            else {
                //num번 말 아래있는 말은 다시 원래좌표에 넣어준다.
                dq[x][y].push_back(tmp);
            }
        }
 
    }
    else if (map[nx][ny] == 1) {
    //이동할 칸이 빨간색인 경우
 
        int size = dq[x][y].size();
        for (int i = 0; i < size; i++) {
            //반대 순서로 넣어줄 것이므로 뒤에것을 빼준다.
            tmp = dq[x][y].back();
            dq[x][y].pop_back();
 
 
            //이동시켜준다.
            dq[nx][ny].push_back(tmp);
 
            //좌표정보 업데이트
            vt[tmp].x = nx;
            vt[tmp].y = ny;
 
            //num번말 위에있는말들과 num번말까지만 이동시키므로 break
            if (tmp == num) break;
        }
    }
 
 
    //말이 4개 이상 쌓이면 true를 리턴
    if (dq[nx][ny].size() >= 4) return true;
    else return false;
}
 
 
 
int turnStart() {
    int turnCnt = 1;
 
 
    while (turnCnt <= 1000) {
        
        bool flag = false;
 
        for (int i = 1; i <= k; i++) {
            flag = move(i);
 
            //말이 4개이상 쌓여서 true값을 리턴받았다면 게임 종료(턴 수를 리턴)
            if (flag) return turnCnt;
        }
        
        turnCnt++;
    }
 
 
    //1000번이 넘으면 -1을 리턴
    return -1;
}
 
 
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie();
 
 
    cin >> n >> k;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            cin >> map[i][j];
        }
    }
 
 
    //1번부터 사용하기 위해 0번째 위치에는 쓰레기값 넣어 놓는다.
    vt.push_back(Horse(-1, -1, -1));
 
 
    int x, y, d;
    for (int i = 1; i <= k; i++) {
        cin >> x >> y >> d;
 
        //말의 정보를 벡터에 넣는다.
        vt.push_back(Horse(x, y, d));
 
        //말이 있는 좌표에 말의 번호를 넣는다.
        dq[x][y].push_back(i);
    }
 
 
    cout <<  turnStart() << '\n';
 
 
    return 0;
}