[백준 17837] 새로운 게임 2 (C++)

문제 링크: https://www.acmicpc.net/problem/17837

17837번: 새로운 게임 2

1. 주의할 점

- 이동할때 이동하는 말 위의 말은 전부 옮겨야 한다

- 벽면도 파란색과 같은 효과라고 했으므로 배열의 크기를 2씩 늘려서 테두리를 2로 감싸도록 한다 -> 배열 범위 밖 고려 안해도 된다

- Cnt(이동 횟수)가 1000을 넘어가면 -1을 출력한다

- 놓치기 쉬운 부분들은 밑에 빨간색으로 처리했다

 

2. 구현

- 현재 이동하려는 말 포함해서 위에 있는 말들을 전부 VV 벡터에 담는다

- 이동하려는 칸이 파란색일 경우, 방향을 바꾸고, 반대쪽 칸도 파란색인 경우 Continue한다

- 원래 위치해 있던 칸에서 VV 벡터만큼 Pop_back()을 수행하여 위에 있는 말들을 없앤다

- 이동하려는 칸이 빨간색인 경우 뒤집어서 놓아야하기 때문에 VV 벡터를 Reverse한다

- 이동하려는 칸에 VV 벡터에 있는 값들을 넣고, 이동하려는 칸에 말이 4개 이상 있다면 Cnt를 출력하고 종료한다

- 말들이 전부 한번씩 이동했다면 Cnt++하고 위의 과정을 반복한다

 

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
struct info {
	int y, x, dir;
};
info tmp;
int arr[14][14], knight, num;
vector<int> chess[14][14];		//해당 칸에 어떤 말들이 있는지 저장
vector<info> v[11];
int dx[5] = { 0,1,-1,0,0 };
int dy[5] = { 0,0,0,-1,1 };

void start() {
	int cnt = 1;
	bool finish = false;
	while (1) {
		if (cnt > 1000) {
			cout << -1;
			break;
		}
		for (int i = 1; i <= knight; i++) {
			int cx = v[i][0].x;
			int cy = v[i][0].y;
			int cd = v[i][0].dir;
			vector<int> vv;
			if (chess[cy][cx].size()>0) {				
				//해당 칸에 있는거 다 넣기
				bool found = false;				
				for (int j = 0; j < chess[cy][cx].size(); j++) {
					if (!found) {
						if (chess[cy][cx][j] == i) {
							found = true;
							vv.push_back(chess[cy][cx][j]);
						}
					}
					else
						vv.push_back(chess[cy][cx][j]);
				}
			}
			int nx = cx + dx[cd];
			int ny = cy + dy[cd];
			int val = arr[ny][nx];
			//파라색
			if (val == 2) {
				int nd;
				//반대도 확인한다
				if (cd == 1)	nd = 2;
				else if (cd == 2) nd = 1;
				else if (cd == 3) nd = 4;
				else if (cd == 4) nd = 3;
				nx = cx + dx[nd];
				ny = cy + dy[nd];
				v[i][0].dir = nd;
				//뒤가 벽or 파란색
				if (arr[ny][nx] == 2)
					continue;
				else
					val = arr[ny][nx];
			}
			//기존에 있던 말 없애기
			for (int k = 0; k < vv.size(); k++) 
				chess[cy][cx].pop_back();
			//빨간색
			if (val == 1) 
				reverse(vv.begin(), vv.end());			
			for(int k=0;k<vv.size();k++) {
				int cidx = vv[k];
				chess[ny][nx].push_back(cidx);
				v[cidx][0].x = nx;
				v[cidx][0].y = ny;
			}			
			if (chess[ny][nx].size() > 3) {
				finish = true;
				break;
			}		
		}
		if (finish) break;
		cnt++;
	}
	if (finish) cout << cnt;
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	cin >> num >> knight;
	for (int i = 0; i < num + 2; i++) 
		for (int j = 0; j < num + 2; j++)
			arr[i][j] = 2;	
	for (int i = 1; i <= num; i++)
		for (int j = 1; j <= num; j++)
			cin >> arr[i][j];
	int x, y, d;
	for (int i = 1; i <= knight; i++) {
		cin >> y >> x >> d;
		tmp.dir = d;
		tmp.x = x;
		tmp.y = y;
		v[i].push_back(tmp);
		chess[y][x].push_back(i);
	}
	start();
	return 0;
}