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

삼성 SW역량 테스트

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

ㄴ새로운 게임

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

 

 

 

l 문제

 

1. 체스판과 말을 이용해서 새로운 게임을 만들기로 했다.

2. 체스판 크기는 N×N 각 칸은 힌색, 빨간색, 파란색 중 하나로 색칠되어있다.

3. 말 사용하는 말의 개수는 K개( 1번 부터 K번 까지 번호 매겨짐 ) 말은 원판모양이고, 하나의 말 위에 다른 말을 올릴 수 있다. 체스판 위에 말 K개를 놓고 시작

4. 턴 턴 한 번은 1번 말부터 K번 말까지 순서대로 이동시키는 것이다. 이동시키는 차례의 말이 가장 아래에 위치한다면 이동이 가능하다.

5. 이동 이동하려는 칸의 색에 따라서 다음의 행동을 한다. 흰색 그 칸으로 이동 그 위치에 이미 말이 있는 경우에는 그 위에 올라탄다. ( A, B가 있는 칸에 C, D가 간다면 A, B, C, D ) 빨간색 그 칸으로 이동한 후에 쌓여있는 순서를 반대로 바꾼다. 그 위치에 이미 말이 있는 경우에는 그 위에 올라탄다. ( A, B가 있는 칸에 C, D가 간다면 A, B, D, C ) 파란색 또는 경계를 벗어남  이동 하지 않고 가장 아래에 있는 말의 이동 방향을 반대로 바꾼다. 바꾼 방향으로 한 칸 이동한 위치의 색이 또 파란색 또는 경계를 벗어난 경우라면 이동하지 않는다.

 

 

l 입력

 

첫째 줄에 체스판의 크기 N, 말의 개수 K가 주어진다.

둘째 줄부터 N개의 줄에 체스판의 색이 주어진다. ( 0: 흰색, 1: 빨간색, 2: 파란색 )

다음 K개의 줄에 말의 정보( 행 번호, 열 번호, 이동 방향 )가 1번 말부터 순서대로 주어진다. 행과 열의 번호는 1부터 시작 이동 방향은 1부터 순서대로 →, ←, ↑, ↓의 의미를 갖는다. 같은 칸에 말이 두 개 이상 있는 경우는 입력으로 주어지지 않는다.

 

 

l 출력

 

말 4개가 쌓인 가장 첫 턴을 출력한다. 그 값이 1,000보다 크거나 절대로 말 4개가 쌓이지 않는 경우에는 -1을 출력한다. 하지만 실제로 말 4개 이상이 쌓인 순간의 턴을 출력해야 답이 맞다. ( 곧 수정 될 것으로 예상 )

 

 

l 풀이

 

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

말 구조체 {    x, y , 방향, 가장 아래인가? } 말 이동 함수 {   이동한 위치의 색에 따라 각각의 행동   2. 경계를 넘거나 파란 칸   3. 하얀 칸   4. 빨간 칸 } 시뮬레이션 함수 {   for ( Round 1 ~ 1000 )       for ( 말 번호 1 ~ K )           1. 가장 아래에 있는가?           말 이동           5. 말이 4개 이상 쌓이면 종료 }

말 정보 관리

1. 1번 부터 K번 까지 말을 순차적으로 접근할 수 있어야 한다. 배열[K] : 말 구조체를 크기가 K인 배열에 차례로 담았다. 2. 말을 쌓을 수 있어야 한다. vector[N+1][N+1] : ( x, y ) 위치에 vector로 { 1, 2, 3번 째 말 } 이런 식으로 담았다. 사실 맨 앞, 맨 뒤의 말의 정보만 필요하므로 말을 쌓을 때 중간의 말은 다 버리고 맨 앞의 말만 쌓거나 vector로 안 하고 [13][13][2] 이런 식으로도 풀이 가능하다.   3. 가장 아래에 있는지 확인 가능해야 한다. 자기 차례가 왔을 때 가장 아래에 있는 말만 움직일 수 있다. 다른 말 위에 올라탈 때 bool 값을 false 순서를 뒤집을 때 맨 앞과 뒤의 bool 값을 바꿔주는 등의 처리가 필요함

문제 조건 오류

이 문제의 조건 "말 4개가 쌓인 가장 첫 턴을 출력한다." 이 조건대로 하면 답이 틀립니다. 말 4개 이상이 쌓인 순간에 바로 턴을 출력하면 됩니다.

 

 

l  코드

 

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

struct horse
{
	int x, y, d;
	bool is_bottom;
} 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];
	// 3. 하얀 칸
	if (color[tx][ty] == 0)
	{
		if (!next.empty()) h[cur.front()].is_bottom = false;
		next.insert(next.end(), cur.begin(), cur.end());
	}
	// 4. 빨간 칸
	else if (color[tx][ty] == 1)
	{
		next.insert(next.end(), cur.rbegin(), cur.rend());
		h[next.back()].is_bottom = false;
		h[next.front()].is_bottom = true;
	}
	h[next.front()].x = h[next.back()].x = tx;
	h[next.front()].y = h[next.back()].y = ty;
	cur.clear();
	return next.size();
}

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

	// 라운드 반복
	for (round = 1; round <= 1000; ++round)
	{
		// 1. 자기 차레에 가장 아래에 있다면 이동
		for (i = 0; i < K; ++i)
		{
			if (h[i].is_bottom)
			{
				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;
		ho.is_bottom = true;
		info[ho.x][ho.y].push_back(i);
	}
	cout << simulation();
	return 0;
}