[백준 문제 C++] 17780 새로운 게임

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

17780번: 새로운 게임

#include <cstdio>
#include <vector>

using namespace std;

typedef struct Horse
{
	int row, col, dir;
	bool isBottom;
}Horse;

const int SIZE = 12;

vector<int> over[11];
Horse horse[11];

int map[SIZE][SIZE];
int unit[SIZE][SIZE];

int dirR[4] = { 0, 0, -1, 1 };
int dirC[4] = { 1, -1, 0, 0 };
int n;

int ReverseOrder(int index)
{
	vector<int> v = over[index];
	int size = v.size();

	if (size <= 1) //위에 쌓인게 없으면 그대로 둔다.
	{
		return index;
	}

	horse[index].isBottom = false;
	int row = horse[index].row;
	int col = horse[index].col;

	for (int i = 0; i < size / 2; ++i)
	{
		int temp = v[i];
		v[i] = v[size - 1 - i];
		v[size - 1 - i] = temp;
	}

	int newIndex = v[0]; //새로운 맨 밑이 탄생하였다.

	over[newIndex] = v;  //새로운 밑으로 말들 배치를 저장해주고,
	over[index].clear(); //기존 것은 제거해준다.

	horse[newIndex].isBottom = true; //새로운 말이 맨 밑이 되었고
	unit[row][col] = v[newIndex];    //현재 unit도 새로운 말 인덱스가 저장된다.

	return newIndex;   //기준 인덱스가 바뀌어야 된다.
}

void TurnAroundDirection(int index)
{
	int dir = horse[index].dir;
	dir = dir / 2 * 2 + (dir + 1) % 2;
	horse[index].dir = dir;
}

bool IsOutOfBound(int row, int col)
{
	return row < 0 || n <= row || col < 0 || n <= col;
}

bool Move(int index, int preRow, int preCol, int newRow, int newCol)
{
	int size = over[index].size();
	int bottom = unit[newRow][newCol];

	unit[preRow][preCol] = 0; //이동 전 기존 좌표는 비워준다.

	for (int i = 0; i < size; ++i) //위에 있는 말들도 함께 이동시킨다.
	{
		int idx = over[index][i];
		horse[idx].row = newRow;
		horse[idx].col = newCol;
	}

	if (bottom != 0) //이동하는 곳에 말이 있다면?
	{
		horse[index].isBottom = false;

		//bottom 벡터 리스트 맨 뒤에 이동 된 index 벡터 리스트를 추가하는 작업이다.
		over[bottom].insert(over[bottom].end(), over[index].begin(), over[index].end());
		over[index].clear();

		if (over[bottom].size() >= 4) //이동 후 말이 4마리 이상이면 게임 오버
		{
			return true;
		}
	}
	else //말이 없으면 그냥 점령한다.
	{
		unit[newRow][newCol] = index;
	}

	return false;
}

bool ProcessFromColor(int index, int step)
{
	Horse h = horse[index];
	
	int d = h.dir;
	int newRow = h.row + dirR[d];
	int newCol = h.col + dirC[d];

	if (IsOutOfBound(newRow, newCol))
	{
		if (step == 0)
		{
			TurnAroundDirection(index);
			return ProcessFromColor(index, step + 1);
		}
		else
		{
			return false;
		}
	}

	switch (map[newRow][newCol])
	{
		case 1:

			index = ReverseOrder(index);
			return Move(index, h.row, h.col, newRow, newCol);

		case 2:

			if (step == 0)
			{
				TurnAroundDirection(index);
				return ProcessFromColor(index, step + 1);
			}
			
			return false;
		default:

			return Move(index, h.row, h.col, newRow, newCol);
	}

	return false;
}

int main()
{
	int row, col, dir;
	int k;
	int moved = 0;
	
	scanf("%d %d", &n, &k);

	for (int i = 0; i < n; ++i)
	{
		for (int j = 0; j < n; ++j)
		{
			scanf("%d", &map[i][j]);
		}
	}

	for (int i = 1; i <= k; ++i) //말 번호는 1~k까지 쓸거지만
	{
		//row, col은 0, 0부터, dir는 0,1,2,3 으로 쓸거라 감소 시켜준다.
		scanf("%d %d %d", &row, &col, &dir);
		row--;
		col--;
		dir--;

		Horse h;
		h.row = row;
		h.col = col;
		h.dir = dir;
		h.isBottom = true;

		horse[i] = h; //말 정보를 등록하고
		unit[row][col] = i; //맵에도 말을 등록해준다.
		over[i].push_back(i); //리스트에는 자신을 먼저 등록해준다.
	}

	while (moved < 1000)
	{
		moved++;

		for (int i = 1; i <= k; ++i)
		{
			if (horse[i].isBottom == false)
			{
				continue;
			}

			bool isFinish = ProcessFromColor(i, 0);
			if (isFinish)
			{
				printf("%d\n", moved);
				return 0;
			}
		}
	}

	printf("-1\n");
	return 0;
}

오랜만에 문제를 하나 풀어봤는데, 머리속으론 로직이 정리되었는데 막상 짜니깐 오류가 생기고..

문제를 잘 못 이해한 부분때문에 이상한 답이 나오며 고생한 문제였다.

 

문제를 정리하면

n x n 맵에 하얀색(0), 빨간색(1), 파란색(2) 의 칸들이 존재하고

k개의 말들이 놓여있으며 말들은 방향을 갖고 있고, 해당 방향으로만 움직일 수 있다.

말들은 작은 숫자 순서대로 움직이고, 다른 말을 만나면 이동한 말(들)은 그 위에 쌓이게 되며

"가장 밑에 있는 말만 움직일 수 있게 된다."

 

하얀색 칸은 그냥 이동, (이동 시 해당 칸에 이미 말이 존재하면 해당 말 위에 올린다.)

빨간색 칸은 이동하기 전에 1,2,3 순서라면 3,2,1 순서로 변경하여 이동,

파란색 칸은 방향을 뒤로 바꾼 후 갈 수 있다면 이동, 불가능하다면 이동하지 않는다.

 

위의 빨간색 조건 때문에 이상한 답이 나왔었는데, 1턴에 모든 말들이 이동할 수 있는지 계속 체크해줘야 한다.

만약 (맨 밑)1, 2로 이루어진 말이 있는데 이 말이 빨간 칸에 가게 되면

2, 1로 바뀌게 된다. 그리고 2번 말이 이동할 수 있게 되며 이것이 1턴에 이루어지는 일들이다. 아래는 예제..

 

그렇게 이 조건을 몰라서 왜 안돼지?? 뻘짓을 하고 말았다고 한다..

 

코드를 설명해보면

우선 맵의 상태를 저장할 map[size][size] 배열과

말들의 위치를 저장할 unit[size][size] 로 따로 관리해주고 있다.

unit은 말의 번호를 저장해두고,

말들에 대해선 horse 배열을 통해 현재 위치 (row, col), 방향, 맨 밑에 있는지를 알아 볼 수 있다.

(사실 체스 말인데.. 그냥 영어 말로함;)

 

unit[1][1] = 1 이라면

horse[1] = { row = 1, col = 1, dir = 어떤 방향, isBottom = true }

(벡터 리스트) over[1] = { 1, 위에 있는 말들 없으면 끝 } 

식으로 해당 인덱스를 대입해서 판별하게 해두었다.

 

vector<int> over[11] 는 위에 쌓이는 말들을 저장하기 위한 리스트로 초기 상태는 자신의 번호만 들어가있다.

ReverseOrder 또는 Move 시에 다른 말위에 올라탈 수 있다면 해당 리스트가 복사되는 형태이다.

 

ProcessFromColor 로직은 길긴한데.. 이렇게 생겼다.

 

1. 방향에 맞게 새로운 좌표를 지정 (d, newRow, newCol 설정)

 

2. 해당 좌표가 IsOutOfBound 라면 방향을 전환 후 이동할 수 있는지 다시 해본다.

(재귀 함수를 이용했는데 step이 0이 아니라면 이미 한번 방향을 돌린 것이고, 그래도 이동이 안되면 가만있는다.)

 

3. 이동한 곳의 map 정보 판별 ( switch (map[newRow][newCol] )

 

 3-1. (빨간 칸) ReverseOrder를 통해 뒤집어 주고, 새로운 맨 밑이 현재 인덱스로 설정하게 해주었다.

   이 함수에서 unit[row][col] 에 대한 말 번호, 맨 밑에 있던 말의 isBottom, 새로운 맨 밑이 된 말의 isBottom

   초기화가 굉장히 중요하다. 순서 바꾸는 건 for에 있음.

 

 3-2. (파란 칸) 방향 전환 후 이동인데, 이미 방향을 바꿨던 경우 (step > 0) 라면 그냥 가만있으면 된다.

 

 3-3. (하얀 칸) 이동한다. 이동 시 이동할 unit 배열을 통해 말이 있는지 없는지 판별한다.

                   기존 말이 없다면 이동한 말이 해당 좌표에 등록되면 되고,

                   기존 말이 있다면 그 말의 맨 위로 올려버리고 운명을 함께 하면 되겠다.

 

 

사실 부족한 코드지만 글을 쓰고, 정리하다보면 좀 더 나아지지 않을까 하는 생각으로 올려봅니다.