[ BOJ 백준 17780번 - 새로운 게임 ] 해설 및 코드

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

 

목적

다음과 같은 체스판에서 말들을 규칙에 따라 이동하여 게임을 진행할 때, 게임이 끝나는 턴의 번호를 출력하자.

접근법

이 프로그램의 동작은 다음과 같은 일련의 과정이 종료조건(4개의 말이 쌓이는 경우 or 턴 번호가 1000을 넘어가는 경우)을 만족할 때까지 반복된다.

 

1. 말의 이동 가능 여부 확인

• 말은 번호 순으로 이동 하는데, 만약 이동시킬 차례의 말이 다른 말 위에 올라가 있는 상태라면 이동할 수 없으며, 차례를 건너 뛰게 된다. (해당 상태는 말의 이동을 처리하는 함수에서 설정하자.)
• 그리고 이동하려는 위치를 검사해야 한다. 만약 체스판의 범위를 벗어나거나, 칸이 파란색이라면 진행 방향을 반대로 하여 이동하게 된다.

2. 말을 이동

• 이동 가능한 체스 말(위에 올라간 모든 말들까지, n*n 벡터 배열로 처리)을 이동시키는데, 이동하려는 칸이 빨간색이라면 말들이 쌓인 순서를 바꾸어서 쌓아야한다.
• 이 과정을 처리하면서 말의 상태(체스판에 놓인 위치와 이동 가능 여부)도 갱신해준다.

 

#include<bits/stdc++.h>
#define f(i,l,r) for(int i=l;i<=r;++i)
using namespace std;
int n,k,a[13][13],dr[]={0,0,0,-1,1},dc[]={0,1,-1,0,0};
bool finished;
vector<int> v[13][13];
struct info{
	int r,c,d;
	bool movable;
}h[11];

bool canMove(int r, int c){
	return r>0&&c>0&&r<=n&&c<=n&&a[r][c]!=2;
}

void move(int i, int nr, int nc){
	h[i].movable=false;
	vector<int> &prev=v[h[i].r][h[i].c], &curr=v[nr][nc];
	
	if(a[nr][nc])reverse(prev.begin(), prev.end());
	
	for(int &j:prev){
		curr.push_back(j);
		h[j].r=nr;
		h[j].c=nc;
	}
	prev.clear();
	h[curr[0]].movable=true;
	finished=curr.size()>3;
}

int sol(){
	f(t,1,1000)f(i,1,k)if(h[i].movable){
		int nr=h[i].r+dr[h[i].d],nc=h[i].c+dc[h[i].d];
		if(!canMove(nr, nc)){
			h[i].d+=(h[i].d&1?1:-1);
			nr=h[i].r+dr[h[i].d],nc=h[i].c+dc[h[i].d];
			if(canMove(nr, nc))move(i,nr,nc);
		}else move(i,nr,nc);
		if(finished)return t;
	}
	return -1;
}


int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin>>n>>k;
	f(i,1,n)f(j,1,n)cin>>a[i][j];
	f(i,1,k){
		cin>>h[i].r>>h[i].c>>h[i].d;
		h[i].movable=true;
		v[h[i].r][h[i].c].push_back(i);
	}
	cout<<sol();
	return 0;
}

 

 

문제 설명과 코드에 대한 피드백은 언제나 환영합니다.

 다양한 의견 댓글로 남겨주세요.