[ Baekjoon ] 17837. 새로운 게임2

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

17837번: 새로운 게임 2

풀이 방법

체스판의 임의의 칸에 여러 개의 말이 쌓여있을 수 있다. 이 정보를 states라는 unordered_map에 저장하도록 한다. key는 칸의 위치를 1차원으로 변환한 값, value는 그 칸에 존재하는 말들의 ID 벡터로 한다. 이때, 해당 벡터를 v라고 하고 크기가 n이라면, v[i]는 v[i+1]~v[n-1]을 업고 있다.

unordered_map< int, vector<int> > states;

 

white() 함수

이동하려는 칸이 흰색이면 업고 있는 말들을 그대로 업고 이동한다. 우선 states에서 현재 위치에 존재하는 말들 중 자기 자신을 찾고, 그 다음에 존재하는 모든 말들을 stack이라는 벡터에 저장한다. 그 후, 현재 위치에서 이동할 말들을 제거한다.

vector<int> stack;
auto itr = states.find(h.pos);
vector<int>& hlist = itr->second;
n = hlist.size();

for(int i=0; i<n; i++){
	if(hlist[i] == h.id){
		for(int j=i; j<n; j++){
			stack.push_back(hlist[j]);
		}
		idx = i;
		break;
	}
}
for(int i=n-1; i>=idx; i--){
	hlist.pop_back();
}

새로 이동한 칸에 대해 states 정보를 업데이트한다.

next_pos = next_r * N + next_c;
itr = states.find(next_pos);
if(itr == states.end()){
	states.insert(make_pair(next_pos, stack));
	for(auto hid: stack){
		horses[hid].update(next_r, next_c);
	}
}
else{
	for(auto hid: stack){
		(itr->second).push_back(hid);
		horses[hid].update(next_r, next_c);		
    }
}

 

red() 함수

이동하려는 칸이 빨간색이면 업고 있는 말들의 순서를 뒤집어 이동한다. 따라서 다음과 같이 stack을 구성한다. 이후 새로 이동한 칸에 대해 states 정보를 업데이트하는 과정은 white() 함수에서와 동일하다.

vector<int> stack;
for(int j=0; j<n; j++){
	if(hlist[j] == h.id){
		idx = j;
		break;
	}
}
for(int j=n-1; j>=idx; j--){
	stack.push_back(hlist[j]);
	hlist.pop_back();
}

 

이동하려는 칸이 파란색이면 말의 방향을 바꾼 후, 해당 방향으로 한칸 이동하는데 그 칸의 색에 따라 다르게 이동한다.

// revert direction
if(h.dir == RIGHT || h.dir == UP) h.update(h.r, h.c, h.dir+1);
else h.update(h.r, h.c, h.dir-1);

next_r = h.r + dr[h.dir];
next_c = h.c + dc[h.dir];
				
// move horse
if(valid(next_r, next_c) && board[next_r][next_c] != BLUE){
	if(board[next_r][next_c] == WHITE) white(h, next_r, next_c);
	else red(h, next_r, next_c);
}

 

전체 코드는 여기서 확인할 수 있다.