백준 17780번 - 새로운 게임

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

17780번: 새로운 게임

문제를 제대로 읽지않아 한참동안 헤매었던 문제였습니다.

턴이 진행되던 중에 말이 4개 이상 쌓이면 게임을 끝내야 하는데 K개와 비교한 것이 문제였습니다.

 

• 필요한 배경지식

std::vector 컨테이너에 대한 이해

 

 

• 문제 해결 방법

Vector를 잘 활용하면 직관적으로 풀어낼 수 있습니다.

선언한 변수의 정보는 다음과 같습니다.

using pii = pair<int,int>;
using dpi = pair<pii,pii>;

int m[12][12]{};
int km[12][12]{};
vector<dpi> kv[10];

m[i][i] : 체스판 정보

km[i][j] : (i,j)좌표에 존재하는 말 중 가장 아래에 위치한 말의 번호

kv[i] : i번째 말 위에 쌓인 말들의 정보 = (i좌표, j좌표, 방향, 말번호)

kv[i]에는 i번째 말의 정보도 포함되며 가장 아래에 위치한 모든 말 중에서 i번째 말이 없다면 kv[i]는 빈 vector가 됩니다.

 

위에서 정의한 변수를 이용하여 move함수에서 한턴을 수행하며 makeK0, makeK1, makeK2함수에서는 각각 체스판의 정보가 0,1,2 일때의 이동을 수행합니다.

 

말의 이동으로 말이 더 쌓이는 경우 vector의 insert함수를 이용해 기존 말의 정보를 추가해 주었고 다음 체스판이 1일때 순서가 바뀌는 경우 rbegin()과 rend() 반복자를 이용해 순서가 바뀐 말들의 정보를 다음 말위에 insert로 추가하거나 다음 말들이 없을 경우 assign을 이용해 변경된 정보를 새로 할당해 주었습니다.

 

 

 

 

• C++ 전체 코드

#include<bits/stdc++.h>
#define xx first
#define yy second
using namespace std;
using pii = pair<int,int>;
using dpi = pair<pii,pii>;

int N,K;
int m[12][12]{};
int km[12][12]{};
vector<dpi> kv[10];
int dy[4] = {0,0,-1,1};
int dx[4] = {1,-1,0,0};

bool makeK0(int cy, int cx, int ny, int nx){
    int ci = km[cy][cx];
    int ni = km[ny][nx];
    km[cy][cx] = -1;
    if(ni==-1) {
        km[ny][nx] = ci;
        kv[ci][0].xx.xx = ny;
        kv[ci][0].xx.yy = nx;
    } else {
        kv[ni].insert(kv[ni].end(), kv[ci].begin(),kv[ci].end());
        kv[ci].clear();
        if(kv[ni].size() >= 4) return true;
    }
    return false;
}

bool makeK1(int cy, int cx, int ny, int nx){
    int ci = km[cy][cx];
    int ni = km[ny][nx];
    km[cy][cx] = -1;
    if(ni==-1) {
        ni = kv[ci].back().yy.yy;
        kv[ni].assign(kv[ci].rbegin(), kv[ci].rend());
        if(ci!=ni) kv[ci].clear();
        km[ny][nx] = ni;
        kv[ni][0].xx.xx = ny;
        kv[ni][0].xx.yy = nx;
    } else {
        kv[ni].insert(kv[ni].end(), kv[ci].rbegin(),kv[ci].rend());
        kv[ci].clear();
        if(kv[ni].size() >= 4) return true;
    }
    return false;
}

bool makeK2(int idx, int cy, int cx, int cdir){
    int ndir = cdir;
    if(cdir==0) ndir = 1;
    else if(cdir==1) ndir = 0;
    else if(cdir==2) ndir = 3;
    else if(cdir==3) ndir = 2;
    kv[idx][0].yy.xx = ndir;
    int ny = cy + dy[ndir];
    int nx = cx + dx[ndir];
    if(ny<0 || nx<0 || ny>=N || nx>=N || m[ny][nx]==2) {
        return false;
    } else if(m[ny][nx]==1){
        return makeK1(cy,cx,ny,nx);
    } else {
        return makeK0(cy,cx,ny,nx);
    }
}

bool move(){
	// 쌓인 말의 개수가 4개 이상이면 true 그렇지 않으면 false를 반환
    for(int i=0; i<K; i++){
        if(kv[i].size()==0) continue;
        int cy = kv[i][0].xx.xx;
        int cx = kv[i][0].xx.yy;
        int cdir = kv[i][0].yy.xx;
        int ny = cy + dy[cdir];
        int nx = cx + dx[cdir];
        if(ny<0 || nx<0 || ny>=N || nx>=N || m[ny][nx]==2){
            if(makeK2(i,cy,cx,cdir)) return true;
        } else if(m[ny][nx] == 1){
            if(makeK1(cy,cx,ny,nx)) return true;
        } else { // m[ny][nx]==0
            if(makeK0(cy,cx,ny,nx)) return true;
        }
    }
    return false;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin>>N>>K;
    for(int i=0; i<N; i++){
        for(int j=0; j<N; j++){
            cin>>m[i][j];
        }
    }

    memset(km,-1,sizeof(km)); // km을 -1로 초기화
    int a,b,c;
    for(int i=0; i<K; i++){
        cin>>a>>b>>c;
        // 좌표와 방향정보가 0부터 시작하도록 함
        a--; b--; c--;
        kv[i].push_back({{a,b},{c,i}});
        km[a][b] = i;
    }
    
    int ans = 1;
    while(!move()){
        ans++;
        if(ans>1000) break;
    }
    
    if(ans>1000) cout<<-1;
    else cout<<ans;
}