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

삼성 SW역량 테스트

https://www.acmicpc.net/workbook/view/2771

ㄴ새로운 게임

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

          풀이: https://11001.tistory.com/26

ㄴ새로운 게임 2

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

 

 

 

l 문제

 

[백준 17780: 새로운 게임] 과 다른 점

가장 아래에 있는 말이 아니여도 이동 할 수 있다. 이동할 땐 마찬가지로 위에 쌓여있는 말과 같이 이동한다. 1 3 5 2 4 순으로 쌓여 있을 때 1 : 1 3 5 2 4 이동 2 : 2 4  이동 3 : 3 5 이동 4 : 4 이동 5 : 5 이동 이렇게 된다.

 

 

l 풀이

 

매 턴 마다 1 ~ K 번 말을 차례로 이동시키면 됩니다.

말 구조체 {    x, y , 방향 } 말의 쌓여있는 순서 정보 vector<int> [x][y] : ( x, y ) 위치에 쌓여있는 말 순서 { ... } 말 이동 함수 {   이동한 칸의 색에 따라 각각의 행동   2. 경계를 넘거나 파란 칸   3. 빨간 칸 - 뒤집기   4. 이동 } 시뮬레이션 함수 {   for ( Round 1 ~ 1000 )       for ( 말 번호 1 ~ K )           1. 말 이동           5. 말이 4개 이상 쌓이면 종료 }

말 이동

( x, y ) 위치에 있는 말의 순서를 가진 배열에서 i 번 째 말의 iterator를 찾아내고 해당 iterator 부터 end 까지 다음 위치로 이동 시킵니다. 빨간 칸인 경우 해당 iterator 부터 end 까지 뒤집어 주고 이동 시킵니다.

 

 

l  코드

 

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;

struct horse
{
	int x, y, d;
} h[10];

int N, K;
int dx[] = { 0, 0, 0, -1, 1 };
int dy[] = { 0, 1, -1, 0, 0 };
int turn[] = { 0, 2, 1, 4, 3 };
int color[13][13];
vector<int> info[13][13];

int move(int i)
{
	int tx = h[i].x + dx[h[i].d];
	int ty = h[i].y + dy[h[i].d];

	// 2. 경계를 넘거나 파란 칸
	if (tx <= 0 || ty <= 0 || tx > N || ty > N || color[tx][ty] == 2)
	{
		// 방향 전환
		h[i].d = turn[h[i].d];

		tx = h[i].x + dx[h[i].d];
		ty = h[i].y + dy[h[i].d];

		// 반대 방향도 파랑
		if (tx <= 0 || ty <= 0 || tx > N || ty > N || color[tx][ty] == 2)
			return 0;
	}
	vector<int> &cur = info[h[i].x][h[i].y];
	vector<int> &next = info[tx][ty];
	auto s = find(cur.begin(), cur.end(), i);

	// 3. 빨간 칸 - 뒤집기
	if (color[tx][ty] == 1)
		reverse(s, cur.end());

	// 4. 이동
	for (auto it = s; it != cur.end(); ++it)
	{
		h[*it].x = tx, h[*it].y = ty;
		next.push_back(*it);
	}
	cur.erase(s, cur.end());
	return next.size();
}

int simulation()
{
	register int round, i, tx, ty, stack_cnt;

	for (round = 1; round <= 1000; ++round)
	{
		for (i = 0; i < K; ++i)
		{
			// 1. 자기 차레에 이동
			stack_cnt = move(i);

			// 5. 말이 4 이상 쌓이면 종료
			if (stack_cnt >= 4) return round;
		}
	}
	return -1;
}

int main()
{
	// freopen("input.txt", "r", stdin);
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> N >> K;
	register int i, j;
	for (i = 1; i <= N; ++i)
		for (j = 1; j <= N; ++j)
			cin >> color[i][j];

	for (i = 0; i < K; ++i)
	{
		horse& ho = h[i];
		cin >> ho.x >> ho.y >> ho.d;
		info[ho.x][ho.y].push_back(i);
	}
	cout << simulation();
	return 0;
}