https://www.acmicpc.net/problem/17780
17780번: 새로운 게임
재현이는 주변을 살펴보던 중 체스판과 말을 이용해서 새로운 게임을 만들기로 했다. 새로운 게임은 크기가 N×N인 체스판에서 진행되고, 사용하는 말의 개수는 K개이다. 말은 원판모양이고, 하
www.acmicpc.net
#include <cstdio>
#include <vector>
using namespace std;
typedef struct Horse
{
int row, col, dir;
bool isBottom;
}Horse;
const int SIZE = 12;
vector<int> over[11];
Horse horse[11];
int map[SIZE][SIZE];
int unit[SIZE][SIZE];
int dirR[4] = { 0, 0, -1, 1 };
int dirC[4] = { 1, -1, 0, 0 };
int n;
int ReverseOrder(int index)
{
vector<int> v = over[index];
int size = v.size();
if (size <= 1) //위에 쌓인게 없으면 그대로 둔다.
{
return index;
}
horse[index].isBottom = false;
int row = horse[index].row;
int col = horse[index].col;
for (int i = 0; i < size / 2; ++i)
{
int temp = v[i];
v[i] = v[size - 1 - i];
v[size - 1 - i] = temp;
}
int newIndex = v[0]; //새로운 맨 밑이 탄생하였다.
over[newIndex] = v; //새로운 밑으로 말들 배치를 저장해주고,
over[index].clear(); //기존 것은 제거해준다.
horse[newIndex].isBottom = true; //새로운 말이 맨 밑이 되었고
unit[row][col] = v[newIndex]; //현재 unit도 새로운 말 인덱스가 저장된다.
return newIndex; //기준 인덱스가 바뀌어야 된다.
}
void TurnAroundDirection(int index)
{
int dir = horse[index].dir;
dir = dir / 2 * 2 + (dir + 1) % 2;
horse[index].dir = dir;
}
bool IsOutOfBound(int row, int col)
{
return row < 0 || n <= row || col < 0 || n <= col;
}
bool Move(int index, int preRow, int preCol, int newRow, int newCol)
{
int size = over[index].size();
int bottom = unit[newRow][newCol];
unit[preRow][preCol] = 0; //이동 전 기존 좌표는 비워준다.
for (int i = 0; i < size; ++i) //위에 있는 말들도 함께 이동시킨다.
{
int idx = over[index][i];
horse[idx].row = newRow;
horse[idx].col = newCol;
}
if (bottom != 0) //이동하는 곳에 말이 있다면?
{
horse[index].isBottom = false;
//bottom 벡터 리스트 맨 뒤에 이동 된 index 벡터 리스트를 추가하는 작업이다.
over[bottom].insert(over[bottom].end(), over[index].begin(), over[index].end());
over[index].clear();
if (over[bottom].size() >= 4) //이동 후 말이 4마리 이상이면 게임 오버
{
return true;
}
}
else //말이 없으면 그냥 점령한다.
{
unit[newRow][newCol] = index;
}
return false;
}
bool ProcessFromColor(int index, int step)
{
Horse h = horse[index];
int d = h.dir;
int newRow = h.row + dirR[d];
int newCol = h.col + dirC[d];
if (IsOutOfBound(newRow, newCol))
{
if (step == 0)
{
TurnAroundDirection(index);
return ProcessFromColor(index, step + 1);
}
else
{
return false;
}
}
switch (map[newRow][newCol])
{
case 1:
index = ReverseOrder(index);
return Move(index, h.row, h.col, newRow, newCol);
case 2:
if (step == 0)
{
TurnAroundDirection(index);
return ProcessFromColor(index, step + 1);
}
return false;
default:
return Move(index, h.row, h.col, newRow, newCol);
}
return false;
}
int main()
{
int row, col, dir;
int k;
int moved = 0;
scanf("%d %d", &n, &k);
for (int i = 0; i < n; ++i)
{
for (int j = 0; j < n; ++j)
{
scanf("%d", &map[i][j]);
}
}
for (int i = 1; i <= k; ++i) //말 번호는 1~k까지 쓸거지만
{
//row, col은 0, 0부터, dir는 0,1,2,3 으로 쓸거라 감소 시켜준다.
scanf("%d %d %d", &row, &col, &dir);
row--;
col--;
dir--;
Horse h;
h.row = row;
h.col = col;
h.dir = dir;
h.isBottom = true;
horse[i] = h; //말 정보를 등록하고
unit[row][col] = i; //맵에도 말을 등록해준다.
over[i].push_back(i); //리스트에는 자신을 먼저 등록해준다.
}
while (moved < 1000)
{
moved++;
for (int i = 1; i <= k; ++i)
{
if (horse[i].isBottom == false)
{
continue;
}
bool isFinish = ProcessFromColor(i, 0);
if (isFinish)
{
printf("%d\n", moved);
return 0;
}
}
}
printf("-1\n");
return 0;
}오랜만에 문제를 하나 풀어봤는데, 머리속으론 로직이 정리되었는데 막상 짜니깐 오류가 생기고..
문제를 잘 못 이해한 부분때문에 이상한 답이 나오며 고생한 문제였다.
문제를 정리하면
n x n 맵에 하얀색(0), 빨간색(1), 파란색(2) 의 칸들이 존재하고
k개의 말들이 놓여있으며 말들은 방향을 갖고 있고, 해당 방향으로만 움직일 수 있다.
말들은 작은 숫자 순서대로 움직이고, 다른 말을 만나면 이동한 말(들)은 그 위에 쌓이게 되며
"가장 밑에 있는 말만 움직일 수 있게 된다."
하얀색 칸은 그냥 이동, (이동 시 해당 칸에 이미 말이 존재하면 해당 말 위에 올린다.)
빨간색 칸은 이동하기 전에 1,2,3 순서라면 3,2,1 순서로 변경하여 이동,
파란색 칸은 방향을 뒤로 바꾼 후 갈 수 있다면 이동, 불가능하다면 이동하지 않는다.
위의 빨간색 조건 때문에 이상한 답이 나왔었는데, 1턴에 모든 말들이 이동할 수 있는지 계속 체크해줘야 한다.
만약 (맨 밑)1, 2로 이루어진 말이 있는데 이 말이 빨간 칸에 가게 되면
2, 1로 바뀌게 된다. 그리고 2번 말이 이동할 수 있게 되며 이것이 1턴에 이루어지는 일들이다. 아래는 예제..
그렇게 이 조건을 몰라서 왜 안돼지?? 뻘짓을 하고 말았다고 한다..
코드를 설명해보면
우선 맵의 상태를 저장할 map[size][size] 배열과
말들의 위치를 저장할 unit[size][size] 로 따로 관리해주고 있다.
unit은 말의 번호를 저장해두고,
말들에 대해선 horse 배열을 통해 현재 위치 (row, col), 방향, 맨 밑에 있는지를 알아 볼 수 있다.
(사실 체스 말인데.. 그냥 영어 말로함;)
unit[1][1] = 1 이라면
horse[1] = { row = 1, col = 1, dir = 어떤 방향, isBottom = true }
(벡터 리스트) over[1] = { 1, 위에 있는 말들 없으면 끝 }
식으로 해당 인덱스를 대입해서 판별하게 해두었다.
vector<int> over[11] 는 위에 쌓이는 말들을 저장하기 위한 리스트로 초기 상태는 자신의 번호만 들어가있다.
ReverseOrder 또는 Move 시에 다른 말위에 올라탈 수 있다면 해당 리스트가 복사되는 형태이다.
ProcessFromColor 로직은 길긴한데.. 이렇게 생겼다.
1. 방향에 맞게 새로운 좌표를 지정 (d, newRow, newCol 설정)
2. 해당 좌표가 IsOutOfBound 라면 방향을 전환 후 이동할 수 있는지 다시 해본다.
(재귀 함수를 이용했는데 step이 0이 아니라면 이미 한번 방향을 돌린 것이고, 그래도 이동이 안되면 가만있는다.)
3. 이동한 곳의 map 정보 판별 ( switch (map[newRow][newCol] )
3-1. (빨간 칸) ReverseOrder를 통해 뒤집어 주고, 새로운 맨 밑이 현재 인덱스로 설정하게 해주었다.
이 함수에서 unit[row][col] 에 대한 말 번호, 맨 밑에 있던 말의 isBottom, 새로운 맨 밑이 된 말의 isBottom
초기화가 굉장히 중요하다. 순서 바꾸는 건 for에 있음.
3-2. (파란 칸) 방향 전환 후 이동인데, 이미 방향을 바꿨던 경우 (step > 0) 라면 그냥 가만있으면 된다.
3-3. (하얀 칸) 이동한다. 이동 시 이동할 unit 배열을 통해 말이 있는지 없는지 판별한다.
기존 말이 없다면 이동한 말이 해당 좌표에 등록되면 되고,
기존 말이 있다면 그 말의 맨 위로 올려버리고 운명을 함께 하면 되겠다.
사실 부족한 코드지만 글을 쓰고, 정리하다보면 좀 더 나아지지 않을까 하는 생각으로 올려봅니다.
'Algorithm > Baekjoon Online Judge' 카테고리의 다른 글
| [백준 문제 C++] 1039 교환 (0) | 2021.07.28 |
|---|---|
| [백준 문제 C++] 1072 게임 (0) | 2021.07.18 |
| [백준 문제 C++] 3109 빵집 (0) | 2021.07.07 |
| [백준 문제 C++] 17386 선분 교차 1 (0) | 2021.05.18 |
| [백준 문제 C++] 17406 배열 돌리기 4 (0) | 2021.05.11 |
