티스토리 뷰
1. 문제 링크
https://www.acmicpc.net/problem/17780
17780번: 새로운 게임
재현이는 주변을 살펴보던 중 체스판과 말을 이용해서 새로운 게임을 만들기로 했다. 새로운 게임은 크기가 N×N인 체스판에서 진행되고, 사용하는 말의 개수는 K개이다. 말은 원판모양이고, 하
www.acmicpc.net
2. 문제 개요
게임은 크기가 N×N인 체스판에서 진행되고, 사용하는 말의 개수는 K개다. 말은 원판 모양이고, 하나의 말 위에 다른 말을 올릴 수 있다. 체스판의 각 칸은 흰색, 빨간색, 파란색 중 하나로 색칠되어있다.
움직일 때 여러 가지 조건이 있을 때, 몇 턴만에 게임이 종료되는지 구하라.
3. 문제 힌트
말들의 모든 정보를 알고 있어야할까?
합쳐질 때 전체를 뒤집는지, 안 뒤집는지로만 나뉘는데...
4. 문제 풀이
이 문제는 알고리즘이 필요 없다. 문제에서 주어진대로 구현하면 된다.
그런데 얼마나 효율적으로 구현할 것인지가 문제.
말을 얹어서 함께 움직이는 것에 중점을 둬 보자.
말의 정보가 바뀌는 것은 말이 있는 흰색 칸에 말이 도착한 경우, 빨간 칸에 말이 도착한 경우다. 그러면 말의 모든 정보를 알고 있어야 할까?
답은 그렇지 않다. 말은 단순히 뒤집히기만 하기 때문에, 말이 쌓여있는 것 중 가장 위의 것과 가장 밑의 것만 알면 된다.
그리고 해당 말이 가장 밑에 있다는 것을 나타내는 어떤 변수가 필요하다.
물론, 입력 크기가 작기 때문에 Deque나, queue, vector 등을 사용해서 모든 말의 정보를 갖고 있어도 될 것 같다.
이렇게 설계를 하고 나서는 문제에서 주어진 순서, 절차대로 진행하도록 구현했다.
밑 5번 코드에서 파란색 or 맵 밖으로 나간경우에 코드가 중복되는 게 있는데, 빨간 블록 도착했을 때, 흰 불록 도착했을 때의 동작을 함수화해 놓으면 깔끔해질 것 같다.
5. 코드
#include <iostream>
#include <vector>
using namespace std;
struct Horse
{
Horse() { bottom = -1, top = -1, count = -1; }
Horse(int b_, int t_, int c_) :bottom(b_), top(t_), count(c_) {}
int bottom, top;
int count;
};
struct Item
{
Item() {}
Item(int y_, int x_, int dir_) :y(y_), x(x_), dir(dir_) {}
int y, x, dir;
};
vector<Item> horseList;
vector<bool>isBottom;
int n, k;
int color[13][13];
Horse map[13][13];
constexpr int dx[] = { 0, 1, -1, 0, 0 };
constexpr int dy[] = { 0, 0, 0, -1, 1 };
int main()
{
cin >> n >> k;
isBottom.resize(k, true);
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= n; ++j)
cin >> color[i][j];
for (int i = 0; i < k; ++i){
Item item;
cin >> item.y >> item.x >> item.dir;
horseList.push_back(item);
map[item.y][item.x] = Horse(i, i, 1);
}
int ans = 0;
bool fin = false;
while (1)
{
++ans;
if (ans > 1000) {
ans = -1;
break;
}
for (int i = 0; i < horseList.size(); ++i)
{
if (isBottom[i] == true)
{
//move
Item next, &cur = horseList[i];
next.y = cur.y + dy[cur.dir];
next.x = cur.x + dx[cur.dir];
if (next.y <= 0 || next.x <= 0 || next.y > n || next.x > n || color[next.y][next.x] == 2) {
if (cur.dir == 1)
cur.dir = 2;
else if (cur.dir == 2)
cur.dir = 1;
else if (cur.dir == 3)
cur.dir = 4;
else if (cur.dir == 4)
cur.dir = 3;
next.y = cur.y + dy[cur.dir];
next.x = cur.x + dx[cur.dir];
if (next.y <= 0 || next.x <= 0 || next.y > n || next.x > n || color[next.y][next.x] == 2)
{
//nothing to do
}
else if (color[next.y][next.x] == 1)
{
next.dir = cur.dir;
if (map[next.y][next.x].count == -1)
{
map[next.y][next.x].top = map[cur.y][cur.x].bottom;
map[next.y][next.x].bottom = map[cur.y][cur.x].top;
map[next.y][next.x].count = map[cur.y][cur.x].count;
isBottom[map[next.y][next.x].top] = false;
isBottom[map[next.y][next.x].bottom] = true;
map[cur.y][cur.x] = Horse();
horseList[map[next.y][next.x].bottom].x = next.x;
horseList[map[next.y][next.x].bottom].y = next.y;
}
else
{
map[next.y][next.x].top = map[cur.y][cur.x].bottom;
isBottom[map[next.y][next.x].top] = false;
map[next.y][next.x].count += map[cur.y][cur.x].count;
map[cur.y][cur.x] = Horse();
}
}
else if (color[next.y][next.x] == 0)
{
next.dir = cur.dir;
if (map[next.y][next.x].count == -1)
{
map[next.y][next.x] = map[cur.y][cur.x];
map[cur.y][cur.x] = Horse();
}
else
{
map[next.y][next.x].top = map[cur.y][cur.x].top;
isBottom[map[cur.y][cur.x].bottom] = false;
map[next.y][next.x].count += map[cur.y][cur.x].count;
map[cur.y][cur.x] = Horse();
}
}
}
else if (color[next.y][next.x] == 1)
{
next.dir = cur.dir;
if (map[next.y][next.x].count == -1)
{
map[next.y][next.x].top = map[cur.y][cur.x].bottom;
map[next.y][next.x].bottom = map[cur.y][cur.x].top;
map[next.y][next.x].count = map[cur.y][cur.x].count;
isBottom[map[next.y][next.x].top] = false;
isBottom[map[next.y][next.x].bottom] = true;
map[cur.y][cur.x] = Horse();
horseList[map[next.y][next.x].bottom].x = next.x;
horseList[map[next.y][next.x].bottom].y = next.y;
}
else
{
map[next.y][next.x].top = map[cur.y][cur.x].bottom;
isBottom[map[next.y][next.x].top] = false;
map[next.y][next.x].count += map[cur.y][cur.x].count;
map[cur.y][cur.x] = Horse();
}
}
else if (color[next.y][next.x] == 0)
{
next.dir = cur.dir;
if (map[next.y][next.x].count == -1)
{
map[next.y][next.x] = map[cur.y][cur.x];
map[cur.y][cur.x] = Horse();
}
else
{
map[next.y][next.x].top = map[cur.y][cur.x].top;
isBottom[map[cur.y][cur.x].bottom] = false;
map[next.y][next.x].count += map[cur.y][cur.x].count;
map[cur.y][cur.x] = Horse();
}
}
if (map[next.y][next.x].count >= 4) {
fin = true;
break;
}
}
}
if (fin)
break;
for (int i = 0; i < k; ++i)
isBottom[i] = false;
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= n; ++j)
{
if (map[i][j].bottom != -1)
{
isBottom[map[i][j].bottom] = true;
horseList[map[i][j].bottom].y = i;
horseList[map[i][j].bottom].x = j;
}
}
}
cout << ans;
return 0;
}
6. 결과
댓글