1. 색깔을 저장한 map, 말을 저장하는 3차원 배열 맵(각 칸마다 4칸만 있으면 됨), 각 칸에 말이 몇개있는지 저장하는 인덱스맵
2. 턴을 계속 진행함.
각 말을 순차적으로 검사함. 이때 각 말들을 몇 번 검사했는지 저장하는 temp 배열을 생성.
방향과 색깔에 맞춰 이동 시킴.
-두번째면 그냥 넘기고 다음 거 검사
-빨강이면 위에서부터 옆으로 이동시킴
-흰색이면 현재 말부터 옆으로 이동시킴
-파랑이나 맵 밖이면 방향을 바꾸고 현재말을 다시 검사함. 단, 이미 두번째 검사라면 방향은 변화시키지 않음.
-어느 순간이든, 4개가 되면 그때의 turn을 리턴.
주의점
-파랑이나 맵 밖이면, 방향을 바꿀때, 두번째 검사라면 방향을 변화시키면 안된다.
-> 현재거 밑에 뭔가가 있을 수 있고, 그 밑에 있는게 방향이 현재 말과 다르다면 이동 후 크게 달라질 수 있기 때문에.
코드
#include <iostream>#include <cstring>#include <vector>#define MAX_WIDTH 13using 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;}