[BOJ]백준 17780/17837번: 새로운 게임, 새로운 게임2

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

17780번: 새로운 게임

삼성 역량테스트 기출문제이면서, 주어진 요구사항대로 코딩하면 되는 단순 구현문제이다.

이 때, 문제에 명시되어 있는 조건들을 헷갈리지 말고 정리하는게 중요하다!!

게임의 룰은 크게

1. N*N 크기의 체스판에서 진행되고, K개의 말이 있다. 

2. 각 칸은 흰색, 빨간색, 파란색 중 하나이다.

3. 한 턴에 1번부터 K번 말까지 전부 순서대로 정해진 이동방향대로 이동을 한다.

4. 말의 이동은 칸에서 가장 아래에 있는 말만, 위에 올라간 말도 한꺼번에 이동해야 한다.

 

그리고 이동하려는 칸에 대해서도 세 가지로 나뉜다.

1. 흰색일 때

 - 이동하려는 칸의 기존에 있는 말 위에 순서대로 쌓는다.

 - ex) ABC -> DE = DEABC

2. 빨간색일 때

 - 이동하려는 칸의 기존에 있는 말 위에 역순으로 쌓는다.

 - ex) ADFG -> ECB = ECBGFDA    /    ABC -> DE = DECBA

3. 파란색일 때 & 체스판을 벗어날 때

 - A번 말의 이동 방향을 반대로 하고 한 칸 이동

 - 반대로 한 뒤 이동하려는 칸이 파란색/체스판을 벗어나면 방향만 반대로, 이동X

 

그래서 위의 상황에서 첫 번째 턴을 진행하면 

두번째 턴을 진행하면

아래와 같이 된다. 이 때 말이 4개가 쌓이는 가장 첫 턴을 구하면 된다.

중요한 것은 턴이 끝났을 때(K개의 말이 이동을 종료했을 때)가 아니라, 말이 이동을 하는 중간 과정에서도 계산을 해줘야 한다는 것이다!!

(이 문제에서는 고려하지 않아도 맞지만 새로운 게임2에서는 조건을 바꾸지 않으면 틀림)

 

새로운 게임 1) 소스코드

#include <cstdio>
#include <vector>
#include <queue>
#include <stack>
using namespace std;
int n, k, map[14][14], ans, dx[] = { 0,1,-1,0,0 }, dy[] = { 0,0,0,-1,1 };
struct piece { int r, c, d; };
piece p[11];
vector<int> v[14][14];
stack<int> s;
queue<int> q;
bool safe(int r, int c) {
	return r > 0 && r <= n && c > 0 && c <= n;
}
int main() {
	scanf("%d%d", &n, &k);
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++)
			scanf("%d", &map[i][j]);
	for (int i = 1; i <= k; i++) {
		scanf("%d%d%d", &p[i].r, &p[i].c, &p[i].d);
		v[p[i].r][p[i].c].push_back(i);
	}
	while (++ans<1000) {
		for (int i = 1; i <= k; i++) {
			vector<int>& cur = v[p[i].r][p[i].c];
			if (cur[0] != i)continue;
			piece t = { p[i].r + dy[p[i].d],p[i].c + dx[p[i].d],p[i].d };
			if (!safe(t.r, t.c) || map[t.r][t.c] == 2) {
				if (p[i].d % 2)p[i].d++;
				else p[i].d--;
				t = { p[i].r + dy[p[i].d],p[i].c + dx[p[i].d],p[i].d };
				if (!safe(t.r, t.c) || map[t.r][t.c] == 2)continue;
				i--;
			}
			else if (map[t.r][t.c]) {
				for (int j = 0; j < cur.size(); j++)s.push(cur[j]);
				cur.clear();
				while (!s.empty()) {
					v[t.r][t.c].push_back(s.top());
					p[s.top()] = { t.r,t.c,p[s.top()].d };
					s.pop();
				}
			}
			else {
				for (int j = 0; j < cur.size(); j++)q.push(cur[j]);
				cur.clear();
				while (!q.empty()) {
					v[t.r][t.c].push_back(q.front());
					p[q.front()] = { t.r,t.c,p[q.front()].d };
					q.pop();
				}
			}
            if (v[t.r][t.c].size() >= 4) {
				printf("%d", ans);
				return 0;
			}
		}
	}
	printf("-1");
	return 0;
}

새로운 게임2) 소스코드

+ 전체적인 흐름은 같지만 중간에 있는 말도 이동할 수 있다는 조건이 추가되었다.

#include <cstdio>
#include <vector>
#include <queue>
#include <stack>
using namespace std;
int n, k, map[14][14], ans, dx[] = { 0,1,-1,0,0 }, dy[] = { 0,0,0,-1,1 };
struct piece { int r, c, d; };
piece p[11];
vector<int> v[14][14];
stack<int> s;
queue<int> q;
bool safe(int r, int c) {
	return r > 0 && r <= n && c > 0 && c <= n;
}
int main() {
	scanf("%d%d", &n, &k);
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++)
			scanf("%d", &map[i][j]);
	for (int i = 1; i <= k; i++) {
		scanf("%d%d%d", &p[i].r, &p[i].c, &p[i].d);
		v[p[i].r][p[i].c].push_back(i);
	}
	while (++ans<1000) {
		for (int i = 1,idx; i <= k; i++) {
			vector<int>& cur = v[p[i].r][p[i].c];
			piece t = { p[i].r + dy[p[i].d],p[i].c + dx[p[i].d],p[i].d };
			if (!safe(t.r, t.c) || map[t.r][t.c] == 2) {
				if (p[i].d % 2)p[i].d++;
				else p[i].d--;
				t = { p[i].r + dy[p[i].d],p[i].c + dx[p[i].d],p[i].d };
				if (!safe(t.r, t.c) || map[t.r][t.c] == 2)continue;
				i--;
			}
			else if (map[t.r][t.c]) {
				for (idx = 0; cur[idx] != i; idx++);
				for (int j=idx; j < cur.size(); j++)s.push(cur[j]);
				while (cur.size() > idx)cur.pop_back();
				while (!s.empty()) {
					v[t.r][t.c].push_back(s.top());
					p[s.top()] = { t.r,t.c,p[s.top()].d };
					s.pop();
				}
			}
			else {
				for (idx = 0; cur[idx] != i; idx++);
				for (int j = idx; j < cur.size(); j++)q.push(cur[j]);
				while (cur.size() > idx)cur.pop_back();
				while (!q.empty()) {
					v[t.r][t.c].push_back(q.front());
					p[q.front()] = { t.r,t.c,p[q.front()].d };
					q.pop();
				}
			}
			if (v[t.r][t.c].size() >= 4) {
				printf("%d", ans);
				return 0;
			}
		}
	}
	printf("-1");
	return 0;
}