[풀이]
중복 순열로 5번의 move를 만든 후 --> 주어진 방향에 맞추어 move하면 된다
[코드]
#include <iostream>
#include <vector>
#define N_MAX 21
using namespace std;
struct marble {
//블록에 관련한 정보 들어 있음
int num = 0; //블록 값
bool exist = false; //블록 존재하는지
marble(int _num, bool _exist) : num(_num), exist(_exist) {};
marble() :num(), exist() {};
void clear() {
this->num = 0;
this->exist = false;
}
};
int N;
marble map[N_MAX][N_MAX];
marble c_map[N_MAX][N_MAX];
int dir_y[4] = { 0,0,1,-1 };
int dir_x[4] = { 1,-1,0,0 };
int max_value = -1;
bool check_range(int y, int x) {
//좌표가 range안에 들어있으면 true, 아닐시 false
if (y < 0 || y >= N || x < 0 || x >= N) return false;
return true;
}
void move_marble(vector<int>& perm, int r) {
for (int i = 0; i < r; i++) {
int dir = perm[i];
if (dir == 0) {
//오른쪽으로 가는 것,맨 오른쪽부터 블록이 있을 시 하나하나옮긴다
for (int y = 0; y < N; y++) {
int stopped_idx = N;
for (int x = N - 1; x >= 0; x--) {
if (map[y][x].num == 0) continue;
int prev_x = x;
while (1) {
int new_x = prev_x + dir_x[dir];
if (!check_range(y, new_x)) break;
if (map[y][new_x].exist) {
//다른 블록이 있음
if (new_x != stopped_idx && map[y][new_x].num == map[y][prev_x].num){
//이미 합쳐진 곳이 아니고 같은 블록 같을 가진 경우
map[y][new_x].num += map[y][prev_x].num;
stopped_idx = new_x; //합쳐졌기 때문에 다른 블록이 이 위치로 오면 안되기에 index저장
map[y][prev_x].clear();
}
break;
}
else {
//다른 블록이 없기 때문에 여기로 옮겨진다
map[y][new_x].num = map[y][prev_x].num;
map[y][new_x].exist = true;
map[y][prev_x].clear();
}
prev_x = new_x;
}
}
}
}
else if (dir == 1) {
//왼쪽으로 가는것.맨 왼쪽에서부터 블록이 있을 시하나하나 옮긴다
for (int y = 0; y < N; y++) {
int stopped_idx = N;
for (int x = 0; x < N; x++) {
if (map[y][x].num == 0) continue; //블록 없음
int prev_x = x;
while (1) {
int new_x = prev_x + dir_x[dir];
if (!check_range(y, new_x)) break;
if (map[y][new_x].exist) {
//다른 블록이 있음
if (stopped_idx != new_x && map[y][new_x].num == map[y][prev_x].num) {
//이미 합쳐진 곳이 아니고 같은 블록 같을 가진 경우
map[y][new_x].num += map[y][prev_x].num;
stopped_idx = new_x; //합쳐졌기 때문에 다른 블록이 이 위치로 오면 안되기에 index저장
map[y][prev_x].clear();
}
break;
}
else {
//다른 블록이 없기 때문에 거기로 옮긴다
map[y][new_x].num = map[y][prev_x].num;
map[y][new_x].exist = true;
map[y][prev_x].clear();
}
prev_x = new_x;
}
}
}
}
else if (dir == 2) {
//아래로 가는 것. 맨 아래에서부터 블록이 있을 시하나씩 움직인다
for (int x = 0; x < N; x++) {
int stopped_idx = N;
for (int y = N - 1; y >= 0; y--) {
if (map[y][x].num == 0) continue; //블록 없음
int prev_y = y;
while (1) {
int new_y = prev_y + dir_y[dir];
if (!check_range(new_y, x)) break;
if (map[new_y][x].exist) {
//다른 블록이 있어서 멈추거나 합쳐 져야 한다
if (stopped_idx != new_y && map[new_y][x].num == map[prev_y][x].num) {
//같은 값의 블록이 있고 이는 합쳐 진 적이 없다
map[new_y][x].num += map[prev_y][x].num;
stopped_idx = new_y; //합쳐 졌기 때문에 index저장
map[prev_y][x].clear();
}
break;
}
else {
//다른 블록이 없어서 거기로 move
map[new_y][x].num = map[prev_y][x].num;
map[new_y][x].exist = true;
map[prev_y][x].clear();
}
prev_y = new_y;
}
}
}
}
else if (dir == 3) {
//위로 가는 것.맨 위부터 하나씩 움직인다
for (int x = 0; x < N; x++) {
int stopped_idx = N;
for (int y = 0; y < N; y++) {
if (map[y][x].num == 0) continue; //블록 없음
int prev_y = y;
while (1) {
int new_y = prev_y + dir_y[dir];
if (!check_range(new_y, x)) break;
if (map[new_y][x].exist) {
//다른 블록이 있어서 멈추거나 합쳐 져야 한다
if (stopped_idx != new_y && map[new_y][x].num == map[prev_y][x].num) {
//같은 값의 블록이 있고 이는 합쳐 진 적이 없다
map[new_y][x].num += map[prev_y][x].num;
stopped_idx = new_y; //합쳐 졌기 때문에 index저장
map[prev_y][x].clear();
}
break;
}
else {
//다른 블록 이 없어서 거기로 이동
map[new_y][x].num = map[prev_y][x].num;
map[new_y][x].exist = true;
map[prev_y][x].clear();
}
prev_y = new_y;
}
}
}
}
}
}
int get_max_value() {
//현재 map에서 가장 큰 값을 반환한다
int ans = -1;
for (int y = 0; y < N; y++) {
for (int x = 0; x < N; x++) {
marble target = map[y][x];
if (ans < target.num) {
ans = target.num;
}
}
}
return ans;
}
void copy_map(marble original[][N_MAX], marble c_original[][N_MAX]) {
for (int y = 0; y < N; y++) {
for (int x = 0; x < N; x++) {
c_original[y][x] = original[y][x];
}
}
}
void permutation(int idx, int r, int depth, vector<int>& perm) {
if (r == depth) {
//중복 순열로 5가지의 숫자를 모으면 전체 블록들을 이동시킨다
copy_map(map, c_map); // c_map에다가 복사를 해 놓는다
move_marble(perm, r); //전체 블록을 이동시킨다
int result = get_max_value(); //현재 map에서 가장 큰 값을 얻는다
if (result > max_value) {
max_value = result;
}
copy_map(c_map, map); //다시 map에다가 복사를 해 놓는다
return;
}
for (int i = 0; i < 4; i++) {
perm[r] = i;
permutation(i, r + 1, depth, perm);
}
}
void solve() {
vector<int> perm(5);
permutation(0, 0, 5, perm);
}
int main() {
cin >> N;
int num;
for (int y = 0; y < N; y++) {
for (int x = 0; x < N; x++) {
cin >> num;
map[y][x].num = num;
if (num > 0) map[y][x].exist = true;
}
}
solve();
cout << max_value << "\n";
}
[총평]
꽤나 시간이 걸렸는데 이유는
"한번의 이동"이 무엇을 의미하는지 제대로 이해하지 않았다는 것이랑
같은 값을 갖는 두 블록이 충돌할 때 라는 것을 안 보고 넘어갔다...
블록을 이동시키는데 있어 다른 방식을 사용한 블로그
https://yabmoons.tistory.com/230
https://jaimemin.tistory.com/660
시작은 미약하게...