17837 새로운게임2 Samsung sw test

알고리즘(구현)

1. 색깔을 저장한 map, 말을 저장하는 3차원 배열 맵(각 칸마다 4칸만 있으면 됨), 각 칸에 말이 몇개있는지 저장하는 인덱스맵
2. 턴을 계속 진행함.
	각 말을 순차적으로 검사함. 이때 각 말들을 몇 번 검사했는지 저장하는 temp 배열을 생성.
		방향과 색깔에 맞춰 이동 시킴.
			-두번째면 그냥 넘기고 다음 거 검사
			-빨강이면 위에서부터 옆으로 이동시킴
			-흰색이면 현재 말부터 옆으로 이동시킴
			-파랑이나 맵 밖이면 방향을 바꾸고 현재말을 다시 검사함. 단, 이미 두번째 검사라면 방향은 변화시키지 않음.
			-어느 순간이든, 4개가 되면 그때의 turn을 리턴.

주의점

-파랑이나 맵 밖이면, 방향을 바꿀때, 두번째 검사라면 방향을 변화시키면 안된다.
	-> 현재거 밑에 뭔가가 있을 수 있고, 그 밑에 있는게 방향이 현재 말과 다르다면 이동 후 크게 달라질 수 있기 때문에.

코드

#include <iostream>
#include <cstring>
#include <vector>
#define MAX_WIDTH 13
 
using namespace std;
 
typedef struct Piece {
	int row;
	int col;
	int direction; // 1: 오 2 : 왼 3 : 위 4 : 아
} Piece;
 
Piece piece[11];
int map[MAX_WIDTH][MAX_WIDTH];
int pieceMap[MAX_WIDTH][MAX_WIDTH][4];
int indexMap[MAX_WIDTH][MAX_WIDTH];
int width, numOfPiece;
 
int getLastTurnNum();
 
int main() {
	cin >> width >> numOfPiece;
	for (int i = 0; i < width; i++) {
		for (int j = 0; j < width; j++) {
			cin >> map[i][j];
		}
	}
	memset(pieceMap, -1, sizeof(pieceMap));
	memset(indexMap, 0, sizeof(indexMap));
	for (int i = 0; i < numOfPiece; i++) {
		cin >> piece[i].row >> piece[i].col >> piece[i].direction;
		piece[i].row--;
		piece[i].col--;
		pieceMap[piece[i].row][piece[i].col][indexMap[piece[i].row][piece[i].col]++] = i;
	}
 
	cout << getLastTurnNum();
}
 
int getLastTurnNum() {
	for (int turn = 1; turn <= 1000; turn++) {
		int temp[10];
		memset(temp, 0, sizeof(temp));
 
		for (int i = 0; i < numOfPiece; i++) {
			if (temp[i] >= 2)
				continue;
			else
				temp[i]++;
 
			int row = piece[i].row;
			int col = piece[i].col;
			int stackIndex = 0;
			int lastIndex = indexMap[row][col];
			for (stackIndex; stackIndex < lastIndex; stackIndex++)
				if (pieceMap[row][col][stackIndex] == i)
					break;
 
			if (piece[i].direction == 1) {
				if (col >= (width - 1) || map[row][col + 1] == 2) {
					if(temp[i] != 2)
						piece[i].direction = 2;
					i--;
				}
				else if (map[row][col + 1] == 1) {
					for (int j = lastIndex - 1; j >= stackIndex; j--) {
						pieceMap[row][col + 1][indexMap[row][col + 1]++] = pieceMap[row][col][j];
						if (indexMap[row][col + 1] >= 4)
							return turn;
						piece[pieceMap[row][col][j]].col++;
						pieceMap[row][col][j] = -1;
						indexMap[row][col]--;
					}
				}
				else if (map[row][col + 1] == 0) {
					for (int j = stackIndex; j < lastIndex; j++) {
						pieceMap[row][col + 1][indexMap[row][col + 1]++] = pieceMap[row][col][j];
						if (indexMap[row][col + 1] >= 4)
							return turn;
						piece[pieceMap[row][col][j]].col++;
						pieceMap[row][col][j] = -1;
						indexMap[row][col]--;
					}
				}
			}
			else if (piece[i].direction == 2) {
				if (col <= 0 || map[row][col - 1] == 2) {
					if (temp[i] != 2)
						piece[i].direction = 1;
					i--;
				}
				else if (map[row][col - 1] == 1) {
					for (int j = lastIndex - 1; j >= stackIndex; j--) {
						pieceMap[row][col - 1][indexMap[row][col - 1]++] = pieceMap[row][col][j];
						if (indexMap[row][col - 1] >= 4)
							return turn;
						piece[pieceMap[row][col][j]].col--;
						pieceMap[row][col][j] = -1;
						indexMap[row][col]--;
					}
				}
				else if (map[row][col - 1] == 0) {
					for (int j = stackIndex; j < lastIndex; j++) {
						pieceMap[row][col - 1][indexMap[row][col - 1]++] = pieceMap[row][col][j];
						if (indexMap[row][col - 1] >= 4)
							return turn;
						piece[pieceMap[row][col][j]].col--;
						pieceMap[row][col][j] = -1;
						indexMap[row][col]--;
					}
				}
			}
			else if (piece[i].direction == 3) {
				if (row <= 0 || map[row-1][col] == 2) {
					if (temp[i] != 2)
						piece[i].direction = 4;
					i--;
				}
				else if (map[row-1][col] == 1) {
					for (int j = lastIndex - 1; j >= stackIndex; j--) {
						pieceMap[row-1][col][indexMap[row-1][col]++] = pieceMap[row][col][j];
						if (indexMap[row-1][col] >= 4)
							return turn;
						piece[pieceMap[row][col][j]].row--;
						pieceMap[row][col][j] = -1;
						indexMap[row][col]--;
					}
				}
				else if (map[row-1][col] == 0) {
					for (int j = stackIndex; j < lastIndex; j++) {
						pieceMap[row - 1][col][indexMap[row - 1][col]++] = pieceMap[row][col][j];
						if (indexMap[row - 1][col] >= 4)
							return turn;
						piece[pieceMap[row][col][j]].row--;
						pieceMap[row][col][j] = -1;
						indexMap[row][col]--;
					}
				}
			}
			else if(piece[i].direction == 4) {
				if (row >= (width - 1) || map[row+1][col] == 2) {
					if (temp[i] != 2)
						piece[i].direction = 3;
					i--;
				}
				else if (map[row+1][col] == 1) {
					for (int j = lastIndex - 1; j >= stackIndex; j--) {
						pieceMap[row + 1][col][indexMap[row + 1][col]++] = pieceMap[row][col][j];
						if (indexMap[row + 1][col] >= 4)
							return turn;
						piece[pieceMap[row][col][j]].row++;
						pieceMap[row][col][j] = -1;
						indexMap[row][col]--;
					}
				}
				else if (map[row+1][col] == 0) {
					for (int j = stackIndex; j < lastIndex; j++) {
						pieceMap[row + 1][col][indexMap[row + 1][col]++] = pieceMap[row][col][j];
						if (indexMap[row + 1][col] >= 4)
							return turn;
						piece[pieceMap[row][col][j]].row++;
						pieceMap[row][col][j] = -1;
						indexMap[row][col]--;
					}
				}
			}
		}
	}
 
	return -1;
}