C++:: boj 17837 < 새로운 게임 2 >

문제의 핵심은 업어서 이동하는 부분에 대한 구현에서 실수없이 잘 하는 것이다. iterator를 다룰 때 조심을 해서 풀자.

insert 함수의 경우 새로운 벡터의 크기가 현재 벡터의 capacity보다 크다면 재할당을 하게 되고 모든 반복자, 레퍼런스들이 무효화 되므로 주의하자.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int N, K, answer;
int dx[5] = {0, 0, 0, -1, 1}, dy[5] = {0, 1, -1, 0, 0};
int changed_dir[5] = {0, 2, 1, 4, 3};
bool finish = false;

int main() {
	cin >> N >> K;
	vector<vector<int>> board(N+1, vector<int>(N+1));
	vector<vector<vector<int>>> objs(N+1, vector<vector<int>>(N+1));
	vector<int> dirs(K+1);
	vector<pair<int, int>> pos(K+1);
	for (int i=1; i<=N; i++) {
		for (int j=1; j<=N; j++) {
			cin >> board[i][j];
		}
	}
	int r, c, dir;
	for (int i=1; i<=K; i++) {
		cin >> r >> c >> dir;
		objs[r][c].push_back(i);// 해당 행렬에 말을 놓아준다.
		pos[i] = {r, c};// 말의 위치 저장
		dirs[i] = dir;// 방향 저장
	}
	while (answer <= 1000 && !finish) {
		for(int i=1; i<=K; i++) {
			int cur_x = pos[i].first, cur_y = pos[i].second;
			int nx = cur_x + dx[dirs[i]], ny = cur_y + dy[dirs[i]];
			if (nx<=0 || ny<=0 || nx>N || ny>N || board[nx][ny]==2) {
            	// 판 밖으로 나가거나 파란 발판이면
				dirs[i] = changed_dir[dirs[i]];
				nx = cur_x + dx[dirs[i]];
				ny = cur_y + dy[dirs[i]];
				if (nx<=0 || ny<=0 || nx>N || ny>N || board[nx][ny]==2) {
               		// 한번 방향 꺽었는데도 밖이거나 파란 발판이면 이동 X
					continue;
				}
			}
			vector<int>::iterator e = objs[cur_x][cur_y].end();
			vector<int>::iterator s = find(objs[cur_x][cur_y].begin(), e, i);
			int size = objs[nx][ny].size();
			objs[nx][ny].insert(objs[nx][ny].end(), s, e);
			if (board[nx][ny] == 1) {// 빨간 발판이면
				reverse(objs[nx][ny].begin() + size, objs[nx][ny].end());
			}
			for (auto iter = s; iter!=e; iter++) {// 현재말과 업은 말 전부 위치 갱신
				pos[*iter] = {nx, ny};
			}
			if (objs[nx][ny].size() >= 4) {// 종료 조건
				finish = true;
				break;
			}
			objs[cur_x][cur_y].erase(s, e);//이전 위치 삭제
		}
		answer++;
	}
	if (answer > 1000) answer = -1;
	cout << answer << "\n";
}