[알고리즘] 백준 17837

백준 17837번 새로운 게임 2

해결 과정 요약

게임말의 정보를 저장할 Mal 구조체를 만들고 게임판을 저장할 m배열,
게임판위에 쌓이는 말들을 나타내줄 vector dq 배열을 선언해준다.

struct Mal{
    int y;
    int x;
    int where; // 어느 방향으로 갈지 나타냄. dy dx 배열과 같이 씀.
};
Mal mal[10];
int N,K,tmp_y,tmp_x;
int m[12][12];
vector<int> dq[12][12];
vector<int> v;
int dy[] = {0, 0, -1, 1};
int dx[] = {1, -1, 0, 0};

벡터 v는 벡터 pop push 를 반복할 경우 생기는 순서 뒤바뀜을 다시 되돌려주기 위해서 필요하다.
말의 정보를 입력받으면서 dq에 말들을 푸시해준다.
매 턴마다 모든 말에 대하여 같은 코드를 반복하게 된다.
말의 다음 위치가 파란색이나 게임판 밖이라면 말의 방향을 바꾸고 말의 다음 위치를 바꾸어준다.
그 후 다시 파란색을 만나거나 게임판 밖이라면 continue를 한다.
빨간색을 만나면 dq.pop 후 dq.push를 i번째 말까지 반복해준다.
하얀색을 만나면 dq.pop 후 v.push 후 v.pop 후 dq.push를 i번째 말까지 반복해준다.

풀이

#include <bits/stdc++.h>
using namespace std;

struct Mal{
    int y;
    int x;
    int where;
};
Mal mal[10];
int N,K,tmp_y,tmp_x;
int m[12][12];
vector<int> dq[12][12];
vector<int> v;
int dy[] = {0, 0, -1, 1};
int dx[] = {1, -1, 0, 0};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    cin >> N >> K;
    for(int i=0; i<N; i++){
        for(int j=0; j<N; j++){
            cin >> m[i][j];
        }
    }
    for(int i=0; i<K; i++){
        cin >> mal[i].y;
        mal[i].y--;
        cin >> mal[i].x;
        mal[i].x--;
        cin >> mal[i].where;
        mal[i].where--;
        dq[mal[i].y][mal[i].x].push_back(i);
    }
    int cnt;
    for(cnt=1; cnt<1001; cnt++){
        for(int i=0; i<K; i++){
            int ny = mal[i].y + dy[mal[i].where];
            int nx = mal[i].x + dx[mal[i].where];
            if(ny < 0 || nx < 0 || ny >= N || nx >= N || m[ny][nx] == 2){
                if(mal[i].where == 0) mal[i].where = 1;
                else if(mal[i].where == 1) mal[i].where = 0;
                else if(mal[i].where == 2) mal[i].where = 3;
                else if(mal[i].where == 3) mal[i].where = 2;
            }
            ny = mal[i].y + dy[mal[i].where];
            nx = mal[i].x + dx[mal[i].where];
            tmp_y = mal[i].y;
            tmp_x = mal[i].x;
            if(ny < 0 || nx < 0 || ny >= N || nx >= N || m[ny][nx] == 2) continue;
            if(m[ny][nx] == 0){
                while(dq[tmp_y][tmp_x].back() != i){
                    v.push_back(dq[tmp_y][tmp_x].back());
                    dq[tmp_y][tmp_x].pop_back();
                }
                v.push_back(dq[tmp_y][tmp_x].back());
                dq[tmp_y][tmp_x].pop_back();
                while(v.size()){
                    dq[ny][nx].push_back(v.back());
                    mal[v.back()].y = ny;
                    mal[v.back()].x = nx;
                    v.pop_back();
                }
            }
            else if(m[ny][nx] == 1){
                while(dq[tmp_y][tmp_x].back() != i){
                    dq[ny][nx].push_back(dq[tmp_y][tmp_x].back());
                    mal[dq[tmp_y][tmp_x].back()].y = ny;
                    mal[dq[tmp_y][tmp_x].back()].x = nx;
                    dq[tmp_y][tmp_x].pop_back();
                }
                dq[ny][nx].push_back(dq[tmp_y][tmp_x].back());
                mal[dq[tmp_y][tmp_x].back()].y = ny;
                mal[dq[tmp_y][tmp_x].back()].x = nx;
                dq[tmp_y][tmp_x].pop_back();
            }
            if(dq[ny][nx].size() >= 4){
                cout << cnt << "\n";
                return 0;
            }
        }
    }
    cout << "-1\n";
    return 0;
}

코멘트

쉽지 않았던 구현문제. 말을 옮길때마다 모든 말의 y,x값을 최신화 시키지 않는 방법이 존재할까?