Problem 문제풀이
함수를 실수 없이 구현하는 능력을 필요로 하는 문제였다.
전략
-
상어가 (0,0)에 있는 물고기를 잡아먹는다.
-
물고기들이 이동한다.
-
상어가 이동한다.
-
2,3을 반복한다.
문제를 풀기 위해 필요한 배열은 두 가지이다.
-
각 번호에 해당하는 물고기의 위치와 방향 정보를 가지고 있는 배열
-
각 공간에 들어가 있는 물고기의 번호를 저장해둔 배열
또한, 함수도 두 가지 필요하다.
-
물고기의 이동을 구현한 함수
-
상어의 이동을 구현한 함수
설계도는 이제 완성되었다. 먼저 배열을 만들어보자.
struct Fish { //물고기 정보가 들어갈 struct
int row;
int col;
int dir;
Fish()
{
}
Fish(int _row, int _col, int _dir) :row(_row), col(_col), dir(_dir) {}
};
Fish* fish = new Fish[17];
int** ocean = new int* [4];
for (int i = 0; i < 4; i++)
{
ocean[i] = new int[4];
}
다음으로 함수를 구현해보자. 물고기는 이동하는 방향을 갖고 있고 이동할 수 없을 경우 45도씩 최대 8번 회전한다.
상어가 있는 칸과 공간 밖으로 나갈 수 없다는 조건에 유의하자. 상어가 있는 칸 혹은 상어에게 먹힌 물고기가 있던 장소는
row와 col값을 -1로 설정해두었다.
int dirR[8] = { -1,-1,-1,0,1,1,1,0 };
int dirC[8] = { 1,0,-1,-1,-1,0,1,1 };
void move(Fish* _fish, int** _ocean)
{
for (int i = 1; i < 17; i++)
{
if (_fish[i].row == -1 && _fish[i].col == -1)
{
continue;
}
for (int j = 0; j < 8; j++)
{
int nR = _fish[i].row + dirR[_fish[i].dir];
int nC = _fish[i].col + dirC[_fish[i].dir];
if (nR >= 0 && nR < 4 && nC >= 0 && nC < 4)
{
if (_ocean[nR][nC] != -1)
{
int target = _ocean[nR][nC];
if (target != 0)
{
_fish[target].row = _fish[i].row;
_fish[target].col = _fish[i].col;
}
_ocean[_fish[i].row][_fish[i].col] = target;
_ocean[nR][nC] = i;
_fish[i].row = nR;
_fish[i].col = nC;
break;
}
}
_fish[i].dir = (_fish[i].dir+1)%8;
}
/*cout << endl;
for (int i = 0; i < 4; i++)
{
for (int j = 0; j < 4; j++)
{
cout << _ocean[i][j] << '\t';
}
cout << endl;
}
cout << endl;*/
}
}
마지막으로 상어의 움직임을 구현해보자.
int solve(int row, int col, Fish* _fish, int** _ocean)
{
int answer = _ocean[row][col];
int dir = _fish[answer].dir;
_fish[answer].row = -1;
_fish[answer].col = -1;
_ocean[row][col] = -1;
move(_fish, _ocean);
/*for (int i = 0; i < 4; i++)
{
for (int j = 0; j < 4; j++)
{
cout << _ocean[i][j]<<'\t';
}
cout << endl;
}*/
_ocean[row][col] = 0;
int maxValue = 0;
for (int i = 1; i < 4; i++)
{
int nR = row + i * dirR[dir];
int nC = col + i * dirC[dir];
if (nR >= 0 && nR < 4 && nC >= 0 && nC < 4)
{
if (_ocean[nR][nC] > 0)
{
Fish* fish = new Fish[17];
int** ocean = new int* [4];
for (int i = 0; i < 4; i++)
{
ocean[i] = new int[4];
for (int j = 0; j < 4; j++)
{
ocean[i][j] = _ocean[i][j];
}
}
for (int i = 0; i < 17; i++)
{
fish[i] = _fish[i];
}
maxValue = max(maxValue, solve(nR, nC, fish, ocean));
}
}
else
{
if (i == 1)
{
return answer;
}
break;
}
}
return answer + maxValue;
}
디버깅을 안하고 맞추고 싶었으나 아직도 자잘한 실수들이 있어서 디버깅을 하게 되었다. 꼼꼼한 코딩 습관을 기르자!