백준 17837번: 새로운 게임 2 (C++)

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

 

 

 

<전체적인 알고리즘>

구현 , 시뮬레이션 문제다. 문제에서 설명되어있는 그대로 구현을 하면 된다. 

설명할 것이 딱히 없어서 코드에 주석처리만 해놓았다.

 

 

 

<전체 코드>

#include<iostream>
#include<vector>

using namespace std;

class ins
{
public:
	int x, y, d;
	ins(int x, int y, int d)
	{
		this->x = x;
		this->y = y;
		this->d = d;
	}
};

int n, k;
int map[14][14];
vector<int> map2[14][14];  //이차원 배열을 vector로 선언 (숫자들 쌓으려고)
vector<ins> chess_piece;  //체스말 정보 저장
int dir[5][2] = { {0,0}, {0,1},{0,-1},{-1,0},{1,0} };

int reverse(int d)  //방향 반대로 전환
{
	if (d == 1)return 2;
	else if (d == 2)return 1;
	else if (d == 3)return 4;
	else return 3;
}
int move_id(int id)  // 해당 id 체스말을 옮기기
{
	int x = chess_piece[id - 1].x;
	int y = chess_piece[id - 1].y;
	int d = chess_piece[id - 1].d;

	int index = 0;
	for (; index < map2[x][y].size(); index++) if (map2[x][y][index] == id) break;  //해당 id의 층 찾기
	
	int nextx = x + dir[d][0];
	int nexty = y + dir[d][1];
	if (nextx < 1 || nexty < 1 || nexty > n || nextx > n)  //넘어가면 방향 전환
	{
		d = reverse(d);
		chess_piece[id - 1].d = d;
		nextx = x + dir[d][0];
		nexty = y + dir[d][1];
		if (map[nextx][nexty] == 2)return 1; // 전환해도 파랑이면 탈출
	}
	
	while (1)  // 파랑일 경우 다시 돌기
	{
		if (map[nextx][nexty] == 0)  //흰색일 때
		{
			int count = map2[x][y].size() - index;
			if (count + map2[nextx][nexty].size() >= 4)return -1;
			for (; index < map2[x][y].size(); index++)  //id와 위에것들 옮기기
			{
				map2[nextx][nexty].push_back(map2[x][y][index]);
				chess_piece[map2[x][y][index] - 1].x = nextx;
				chess_piece[map2[x][y][index] - 1].y = nexty;
			}
			for (int i = 0; i < count; i++)map2[x][y].pop_back();  // 옮긴 만큼 없애기
			return 1;
		}
		else if (map[nextx][nexty] == 1)  //빨강일 때
		{
			int count = map2[x][y].size() - index;
			if (count + map2[nextx][nexty].size() >= 4)return -1;
			for (int i = map2[x][y].size() - 1; i >= index; i--)  //id와 위에것들 역순으로 옮기기
			{
				map2[nextx][nexty].push_back(map2[x][y][i]);
				chess_piece[map2[x][y][i] - 1].x = nextx;
				chess_piece[map2[x][y][i] - 1].y = nexty;
			}
			for (int i = 0; i < count; i++)map2[x][y].pop_back();  // 옮긴 만큼 없애기
			return 1;
		}
		else  //파랑
		{

			d = reverse(d);
			chess_piece[id - 1].d = d;
			nextx = x + dir[d][0];
			nexty = y + dir[d][1];
			if (map[nextx][nexty] == 2)return 1; // 전환해도 파랑이면 탈출
			if (nextx < 1 || nexty < 1 || nextx > n || nexty > n)return 1;
		}
	}
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	cin >> n >> k;
	for (int i = 1; i <= n; i ++)
	{
		for (int j = 1; j <= n; j++)
		{
			cin >> map[i][j];
		}
	}
	for (int i = 1; i <= k; i++)
	{
		int x, y, d;
		cin >> x >> y >> d;
		map2[x][y].push_back(i);   //이차원 배열에 체스말 위치시키기
		chess_piece.push_back(ins(x,y,d));  //체스말 정보 저장
	}
	int result = 0;
	while (1)
	{
		for (int i = 0; i < k; i++)
		{
			int id = i + 1;
			if (move_id(id) == -1)  //움직이기
			{
				cout << result + 1;
				return 0;
			}
		}
		result++;
		if (result > 1000)  //1000번 넘으면 종료
		{
			cout << "-1";
			return 0;
		}
	}
	cout << "error";

	return 0;
}

 

 

 

궁금하신 점은 댓글에 남겨주시면 답변드리겠습니다.