BOJ 17837 : 새로운 게임 2 - C++

김정욱·2021년 4월 7일
0

Algorithm - 문제

목록 보기
208/249

새로운 게임

코드

#include <cstdio>
#include <vector>
#include <queue>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <set>
#include <deque>
#include <numeric>
#include <map>
#define ll long long
using namespace std;
// 0914 ~ 1049
int N,K,ans;
int dx[4] = {1, -1, 0, 0}; // 우 좌 상 하
int dy[4] = {0, 0, -1, 1};
int board[15][15]; // {말의 번호, 방향}
deque<int> horse[15][15]; // {말의 번호, 방향}
vector<pair<pair<int,int>,int>> v;
int reverseDir(int d){
    if(d == 0) return 1;
    if(d == 1) return 0;
    if(d == 2) return 3;
    return 2;
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> N >> K;
    for(int i=1;i<=N;i++)
        for(int j=1;j<=N;j++)
            cin >> board[i][j];
    for(int i=1;i<=K;i++)
    {
        int r,c,d;
        cin >> r >> c >> d;
        horse[r][c].push_back(i);
        v.push_back({{r,c},d-1});
    }
    while(true)
    {
        ans++;
        for(int i=0;i<v.size();i++)
        {
            if(horse[v[i].first.first][v[i].first.second].size()>=4) goto stop;
            int dir = v[i].second;
            int ny = v[i].first.first + dy[dir];
            int nx = v[i].first.second + dx[dir];
            // 범위를 벗어나면 파란색 블록처럼 처리
            if(nx<1 or ny<1 or nx>N or ny>N){
                dir = reverseDir(dir);
                v[i].second = dir; // 바뀐 dir 저장
                i--;
                continue;
            }
            auto tmp = horse[v[i].first.first][v[i].first.second];
            vector<int> ttmp;
            for(int a=tmp.size()-1;a>=0;a--)
            {
                ttmp.push_back(tmp[a]);
                horse[v[i].first.first][v[i].first.second].pop_back();
                if(tmp[a] == i+1) break;
            }
            /* 하얀 블록이면 idx위로 전부 이동 */
            if(board[ny][nx] == 0){
                for(int a=ttmp.size()-1;a>=0;a--)
                {
                    horse[ny][nx].push_back(ttmp[a]);
                    v[ttmp[a]-1].first = {ny,nx}; // 좌표 갱신
                }
            }else if(board[ny][nx] == 1){
                /* 빨간 블록이면 idx위로 이동하는데 순서 바꾸기 */
                for(int a=0;a<ttmp.size();a++)
                {
                    horse[ny][nx].push_back(ttmp[a]);
                    v[ttmp[a]-1].first = {ny,nx};
                }
            }else if(board[ny][nx] == 2){
                /* 파란색이면 방향전환 + 1칸이동 */
                dir = reverseDir(dir);
                v[i].second = dir; // 바뀐 dir 저장
                int nny = v[i].first.first + dy[dir];
                int nnx = v[i].first.second + dx[dir];
                // ttmp 제자리
                for(int a=ttmp.size()-1;a>=0;a--)
                    horse[v[i].first.first][v[i].first.second].push_back(ttmp[a]);
                // 벗어나거나 또 파란색이면 pass
                if((nny<1 or nnx<1 or nnx>N or nny>N) or (board[nny][nnx] == 2)){
                    continue;
                }
                // 하얀색이거나 빨간색이면 다시 이 말에 대해 수행시킴
                i--;
                continue;
            }
            // board[][]가 2 경우에는 horse의 움직임이 당장 없으니 ny,nx에 대해 사이즈 검사
            if(horse[ny][nx].size()>=4) goto stop;
        }
        if(ans > 1000){
            ans = -1;
            goto stop;
        }
    }
    stop:;
    cout << ans;
    return 0;
}
  • 핵심
    • 다음 이동하는 칸blue인 경우 새로운 방향에 대한 새로운 좌표(nny, nnx)에 대해 다시 한 번 다음 칸을 검사하고 white / red이면 다시 해당 말에 대해 검사하게 i--수행해야 한다
    • 반복문시작하고 끝날 때 horse.size() >=4 인것을 검사해야 한다
profile
Developer & PhotoGrapher

0개의 댓글