문제 요약
환경
- 4*4 크기의 격자에 물고기 16마리(1번~16번)가 있다.
- 방향은 8개가 있다.(↑, ↖, ←, ↙, ↓, ↘, →, ↗)
- 상어가 물고기를 먹으면, 해당 물고기의 위치와 방향을 갖게 된다.
초기값
- 16칸의 격자를 꽉채운 물고기들의 정보를 준다(번호와 방향)
- 상어는 (0,0) 위치의 물고기를 먹는다.
1번의 단계에서 일어나는 일
1. 물고기들의 대이동
번호가 작은 물고기들부터 이동을 한다. 물고기는 한 칸을 이동할 수 있고, 이동할 수 있는 칸은 빈 칸과 다른 물고기가 있는 칸, 이동할 수 없는 칸은 상어가 있거나, 공간의 경계를 넘는 칸이다. 각 물고기는 방향이 이동할 수 있는 칸을 향할 때까지 방향을 45도 반시계 회전시킨다. 만약, 이동할 수 있는 칸이 없으면 이동을 하지 않는다. 그 외의 경우에는 그 칸으로 이동을 한다. 물고기가 다른 물고기가 있는 칸으로 이동할 때는 서로의 위치를 바꾸는 방식으로 이동한다.
2. 상어의 이동
물고기의 이동이 모두 끝나면 상어가 이동한다. 상어는 방향에 있는 칸으로 이동할 수 있는데, 한 번에 여러 개의 칸을 이동할 수 있다. 상어가 물고기가 있는 칸으로 이동했다면, 그 칸에 있는 물고기를 먹고, 그 물고기의 방향을 가지게 된다. 이동하는 중에 지나가는 칸에 있는 물고기는 먹지 않는다. 물고기가 없는 칸으로는 이동할 수 없다. 상어가 이동할 수 있는 칸이 없으면 공간에서 벗어나 집으로 간다.(종료) 상어가 이동한 후에는 다시 물고기가 이동하며, 이후 이 과정이 계속해서 반복된다.
아이디어
격자에 물고기의 번호, 위치를 관리를 하며 물고기 번호로 위치를 알 수 있는 배열을 동시에 관리를 했다.
그리고 dfs적으로 상어의 움직임을 모든 경우를 다 방문하여, 가장 좋은 경우를 선정했다.
dfs적으로 움직일 땐, 재귀함수를 썼으며 상어의 위치, 물고기의 위치 등을 부모 함수에선 유지를 하며 다음단계 재귀에 의해 바뀌는 메모리들을 copy로 새로 할당했다.
왜 배열로 물고기의 위치 관리를 병행했는가
번호가 낮은 물고기서부터 이동을 하기 때문에 번호순으로 바로 위치를 알아낼 수 있어야한다고 생각했다.
배열로 물고기의 위치 관리를 병행하는 걸 비추하는 이유
쓸모 없음
이 공간은 매우 작다... 어차피 지금 존재하는 물고기 중 가장 작은거/ 혹은 ?번 이상이며 가장 작은거를 찾는 max 연산 해봤자 16개 공간만 훑으면 된다.
그리고 결론적으로 이렇게 해봤는데 0ms 나오는 거 보면... direct access가 필요가 없다...
이유는 상어가 0,0에서 출발해서 자기가 먹을 수 있는 마지막 물
죽노동
위치 -> 물고기 인 2차원 공간과 물고기 -> 위치 인 1차원 배열을 동시에 관리하는데, 이 consistency를 맞추는 게 정말 죽노동이라 느껴졌다.... 소스 길이도 엄청 길어져서 어디서 틀렸는지 파악도 안되고...
삽질1. 물고기가 없는 칸으로는 이동할 수 없다.
이게 "상어가 움직일 수 있는 방향 중에 물고기가 없는 칸을 마주칠 시 종료한다."로 구현이 되어있길래 화이트 디버깅을 하며 코드를 추가해줬는데 기존 코드가 삭제가 안돼있어서 시간을 많이 허비했다.
삽질2. dfs의 return 값(기본)
자신이 부모?로부터 받아온 값을 유지를 하면서 자식함수들이 받아온 값 중 가장 큰 걸 더하는 기본적인 내용인데... 부모로부터 받아온 값에 바로 바로 자식 리턴을 적용해버리니 다음 자식한테 부모로부터 받아온 값을 전달할 때 너무 커져있는 문제가 생겼다.
소스
(매우 길어 추천하지 않습니다.)
#include<iostream>
#include<iomanip>
#include<math.h>
using namespace std;
//방향은 0-7로 매핑
int di[] = { -1,-1,0,1,1,1,0,-1 };
int dj[] = { 0 ,-1,-1,-1,0,1,1,1 };
struct pos {
int i, j;
pos(int ii, int jj) : i(ii), j(jj) {};
pos() : i(-1), j(-1) {};//dead fish
};
bool in_box(int i, int j) {
return i >= 0 && i < 4 && j >= 0 && j < 4;
}
bool in_box(pos p) {
int i = p.i, j = p.j;
return i >= 0 && i < 4 && j >= 0 && j < 4;
}
class fish {
public:
int n, d;
fish(int nn, int dd) : n(nn), d(dd) {};
fish() :n(-1), d(-1) {};//dead fish
bool calc_dir(pos mypos,pos shark) {
int origin_d = this->d;
int i = mypos.i, j = mypos.j, sh_i = shark.i, sh_j = shark.j;
//cout << "calc_dir : " << i << "," << j << "," << sh_i << "," << sh_j<<","<<this->d << endl;
//갈 수 있으면 true, 갈 수 없을 때를 대비해서 횟수 돌아오게 잡음
for (int ctr = 0; ctr < 9; ctr++) {
int ci = i + di[d], cj = j + dj[d];
//cout << ctr <<" : "<<ci<<" : "<<cj<< endl;
if (in_box(ci, cj) && !(sh_i == ci && sh_j == cj)) {
return true;
}
this->roll_d();
}
this->d = origin_d;
return false;
}
void roll_d() {
d++;
if (d == 8) d = 0;
}
};
/*
void print_tab(fish tab[4][4],pos lvng_fish[17]) {
for (int i = 0; i < 4; i++) {
for (int j = 0; j < 4; j++) {
cout <<setw(8)<< tab[i][j].n << "," << tab[i][j].d;
}
cout << endl;
}
for (int i = 1; i <= 16; i++) {
cout << setw(6) << i << "번:" << lvng_fish[i].i << "," << lvng_fish[i].j;
}
cout<<endl << "=======================" << endl;
}
*/
pair<pos, int> eat_fish(int fn,fish tab[4][4], pos lvng_fish[17],pos shark,int shark_d,int ctr) {
int i = lvng_fish[fn].i, j = lvng_fish[fn].j;
//cout << "물고기를 먹는 중 : " << fn << "," << i << "," << j <<","<<","<<shark.i<<","<<shark.j<<","<<shark_d<<","<<ctr<< endl;
//print_tab(tab, lvng_fish);
//상어의움직임
shark.i = i; shark.j = j;
//상어 방향 바뀜
shark_d = tab[i][j].d;
//물고기 죽음
tab[i][j] = fish();
lvng_fish[fn] = pos();
return pair<pos, int>(shark, shark_d);
}
int one_round(fish tab[4][4], pos lvng_fish[17], int sum_etable, pos shark, int shark_d, int ctr) {
//cout << "one round begin : " << shark.i << "," << shark.j << "," << shark_d << "," << sum_etable << "," << ctr << endl;
//print_tab(tab, lvng_fish);
//물고기 움직
for (int f_n = 1; f_n <= 16; f_n++) {
pos f_p = lvng_fish[f_n];//fish pos
if (f_p.i != -1) {
fish f = tab[f_p.i][f_p.j];
//cout << "물고기를 보는 중.. " << f_n<<","<<f.n<<","<<f_p.i<<","<<f_p.j<<"\t";
if (f.calc_dir(f_p, shark)) {
int ci = f_p.i + di[f.d], cj = f_p.j + dj[f.d];//움직이고자 하는 곳
if (tab[ci][cj].n == -1) {//비어있으면 쉽게 들감
tab[ci][cj] = f;
lvng_fish[f.n] = pos(ci, cj);
//죽은거랑 스왑
tab[f_p.i][f_p.j] = fish(-1, -1);
//cout << ci << "," << cj << "에 쉽게 들어감" << endl;
}
else {
fish tomo = tab[ci][cj];
tab[f_p.i][f_p.j] = tomo;
lvng_fish[tomo.n] = pos(f_p.i, f_p.j);
//cout << ci << "," << cj << "," << tomo.n << "와 swap" << endl;
tab[ci][cj] = f;
lvng_fish[f.n] = pos(ci, cj);
}
}
//print_tab(tab, lvng_fish);
}
}
//cout << "fish move end" << endl;
//print_tab(tab, lvng_fish);
//상어가 움직
int ret_sum_etable = sum_etable;
for (int k = 1; k <= 3; k++) {
pos next_shark = pos(shark.i + di[shark_d] * k, shark.j + dj[shark_d] * k);
//cout << "먹을 수 있는지 검토중 : " << next_shark.i << "," << next_shark.j << "," << ctr <<","<<k<< endl;
if (!in_box(next_shark) ) {
break;
}
if (tab[next_shark.i][next_shark.j].n == -1) {
//cout << "물고기가 없어용" << endl;
continue;
}
if (tab[next_shark.i][next_shark.j].n != -1) {
//물고기가있다면
//테이블을 복제한 후 상어를 옯기고 물고기를 먹고 dfs
fish child_tab[4][4];
copy(&tab[0][0], &tab[0][0] + 4 * 4, &child_tab[0][0]);
pos child_lvng_fish[17];
copy(&lvng_fish[0], &lvng_fish[0] + 17, &child_lvng_fish[0]);
fish target = tab[next_shark.i][next_shark.j];
pair<pos, int> shark_res = eat_fish(target.n, child_tab, child_lvng_fish, shark, shark_d, ctr);
pos child_shark = shark_res.first;
int child_shark_d = shark_res.second;
int child_sum_eatable = sum_etable + target.n;
//cout << "다음 함수 호출 직전 : ctr : " << ctr << "," << child_sum_eatable << "," << sum_etable << endl;
ret_sum_etable = max(ret_sum_etable, one_round(child_tab, child_lvng_fish, child_sum_eatable, child_shark, child_shark_d, ctr + 1));
}
}
//cout << ctr << "단계가 끝났습니다 : " << ret_sum_etable << endl;
return ret_sum_etable;
}
int main() {
fish tab[4][4];
pos lvng_fish[17];
int a, b;
for (int i = 0; i < 4; i++) {
for (int j = 0; j < 4; j++) {
cin >> a >> b;
tab[i][j] = fish(a, b-1);
lvng_fish[a] = pos(i, j);
}
}
int sum_eatable = 0;
//0,0에가서 먹음
int t_f_n = tab[0][0].n,t_f_d = tab[0][0].d;//target fish number
sum_eatable += t_f_n;
pos shark = pos(0, 0);
int shark_d = t_f_d;
lvng_fish[t_f_n] = pos();
tab[0][0] = fish();
sum_eatable = one_round( tab, lvng_fish, sum_eatable,shark, shark_d,1);
cout << sum_eatable << endl;
}