BJ17837 새로운게임2

BJ17837 새로운게임2

2020.02.09

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

Solution

• 2차원 vector horseInfo를 이용해서 해당 칸에 있는 말들의 번호와 방향을 pair로 순서대로 담았다.
• 1차원 vector horse를 이용해서 k번말의 위치(r,c)를 pair로 담았다.
• getResult 함수 : 1000 번 돌리면서 말을 움직였을 때 4개 이상 올라가는 경우가 생기면 그때의 t를 return 해서 결과를 얻고 만약 1000번동안 없으면 -1을 리턴하는 함수. 1번 돌릴 때 1번말 ~ K번말까지 돌린다.
• Move 함수 : horse의 idx k 를 받아서 이동시키고 이동한 곳의 말의 수를 리턴하는 함수

1시간 반정도 소요되었는데, 문제를 잘못읽었다. (4이상이면 되는데 K이상일 때 라고 잘못 생각하였다.)

더 꼼꼼하게 읽어야 한다.

두번째는 구현과정에서 처음에 함수의 동작을 세밀하게 설계하지 않고 바로 코딩으로 들어갔더니 이전 값들, 다음 값들을 수정해주는 부분에서 오류가 발생하였다. 꼼꼼하게 함수의 동작을 설계하고 코딩하는 습관을 들이자.

자료구조가 복잡하게 있는 경우에 이를 잘 관리하고(수정) 사용하는 과정에 집중해야 한다.

//! 2020.02.09
// TODO BJ17837_새로운게임2
#include<cstdio>
#include<vector>

using namespace std;

const int MAX = 20;
const int dx[4] = {1,-1,0,0};
const int dy[4] = {0,0,-1,1};
const int B = 2;
const int R = 1;
const int W = 0;
int inMap[MAX][MAX];

int N,K;

vector <pair<int,int>> horseInfo[MAX][MAX];
vector <pair<int,int>> horse;

int move(int k){
    int y = horse[k].first;
    int x = horse[k].second;

    int idx = 0;
    while(horseInfo[y][x][idx].first != k) idx++;

    int dir = horseInfo[y][x][idx].second;
    int nextY = y+dy[dir];
    int nextX = x+dx[dir];

    if(inMap[nextY][nextX]==B){
        if(dir==1) dir = 0;
        else if(dir==0) dir = 1;
        else if(dir==2) dir = 3;
        else if(dir==3) dir = 2;
        nextY = y+dy[dir];
        nextX = x+dx[dir];
        horseInfo[y][x][idx].second = dir;
    }

    if(inMap[nextY][nextX]==B) return horseInfo[y][x].size();

    int sizeH = horseInfo[y][x].size();
    if(inMap[nextY][nextX]==W){
        for(int i=idx;i<sizeH;i++){
            horseInfo[nextY][nextX].push_back(horseInfo[y][x][i]);
            horse[horseInfo[y][x][i].first].first = nextY;
            horse[horseInfo[y][x][i].first].second = nextX;
        }
    }else{
        for(int i=sizeH-1;i>=idx;i--){
            horseInfo[nextY][nextX].push_back(horseInfo[y][x][i]);
            horse[horseInfo[y][x][i].first].first = nextY;
            horse[horseInfo[y][x][i].first].second = nextX;
        }
    }
    for(int i=idx;i<sizeH;i++){
        horseInfo[y][x].pop_back();
    }

    return horseInfo[nextY][nextX].size();
}

int getResult(){
    for(int t=1;t<=1000;t++){
        for(int k=0;k<K;k++){
            if(move(k)>=4) return t;
        }
    }
    return -1;
}

int main(){
    scanf("%d %d",&N,&K);
    for(int i=0;i<=N+1;i++){
        inMap[i][0] = 2;
        inMap[i][N+1] = 2;
        inMap[0][i] = 2;
        inMap[N+1][i] = 2;
    }

    for(int i=1;i<=N;i++){
        for(int j=1;j<=N;j++){
            scanf("%d",&inMap[i][j]);
        }
    }

    for(int k=0;k<K;k++){
        int r,c,dir;
        scanf("%d %d %d",&r,&c,&dir);
        horseInfo[r][c].push_back(make_pair(k,dir-1));
        horse.push_back(make_pair(r,c));
    }

    printf("%d\n",getResult());
    return 0;
}