1) 문제 분석
아기 상어의 현재 상태에 따라 조건들이 달라지는 문제이기 때문에 아기 상어를 하나의 클래스로 작성하면 더 읽기 편하고 잘 정리된 코드가 될 것 같았다.
문제 해결에 필요한 상어 상태는
1)현재 위치 2)현재 크기 3)다음 크기로 가기 위해 먹어야 할 물고기 수 4)움직인 시간(초) 정도가 있다.
가장 큰 문제는 상어의 현재 위치에서 가장 가까운 물고기를 찾아야 한다는 것이다. 이를 위해, 현재 상어의 위치에서 bfs를 수행하고 만약 물고기를 만난다면 그 물고기를 먹으러 가는 함수를 작성하기로 하였다.
2) 알고리즘
그런데 여기서 거리가 같은 물고기가 여러 마리 있을 수 있는데, 문제에서 거리가 같다면 가장 위, 그리고 가장 왼쪽의 물고기를 먼저 먹는다는 조건이 있다. 처음에는 bfs를 수행하면서 물고기를 만나면 bfs를 중단하고, 같은 depth에 다른 물고기가 있는지 queue에서 확인하는 식으로 하려고 했다. 그런데 만약 bfs를 수행하는 방향을 위,왼쪽,오른쪽,아래와 같이 하면 같은 거리만큼 떨어진 물고기가 여러 개 있어도 자연스럽게 가장 위에서, 그리고 가장 왼쪽에 위치한 물고기를 먼저 찾을 것이라고 생각하였다.
3) 코드-첫 번째 시도
코드가 좀 길다
#include <iostream>
#include <queue>
using namespace std;
//position (x,y), depth in the bfs tree
typedef struct pos{
int x;
int y;
int depth;
}pos;
//baby shark
class baby_shark{
private:
int r, c; //current position of the shark
int size; //current size of the shark
int exp; //number of fish eaten
public:
int sec; //amount of time used in moving around
/**
* initialize the state of the shark with the current location
* @param x: xth row
* @param y yth column
*/
void initialize(int x, int y){
r=x; c=y;
size = 2;
exp = 0;
sec = 0;
}
/**
* find fish that the baby shark can eat
* @param space: 2d integer array that shows the state of the space the shark is in
* @param n: size of the space (n*n)
* @return true if there is a fish to eat, false if there is no fish to eat
*/
bool find_fish(int** space, int n){
pos cur, next;
int x,y;
queue<pos> q;
bool** found; //2d bool array that tells if (i,j) is already accessed or not
//initialize found array
found = new bool*[n];
for(int i=0; i<n; i++){
found[i] = new bool[n];
for(int j=0; j<n; j++)
found[i][j] = false;
}
//start searching for fish from the current location of the shark
cur.x = r; cur.y = c; cur.depth = 0;
q.push(cur);
//search for fish that is closest to the shark using bfs
while(!q.empty()){
cur = q.front(); q.pop();
x = cur.x; y = cur.y;
next.depth = cur.depth + 1;
//search upwards
//check if there is a space upwards & not accessed yet && there is no fish larger than the shark
if(x-1>=0 && !found[x-1][y] && space[x-1][y]<=size){
next.x = x-1; next.y = y;
found[x-1][y] = true;
//push the newly accessed space to the queue
q.push(next);
//check if there is a fish that can be eaten by the shark
if(space[x-1][y]>0 && space[x-1][y]<size)
//stop bfs
break;
}
//search leftwards
//check if there is a space leftwards & not accessed yet && there is no fish larger than the shark
if(y-1>=0 && !found[x][y-1] && space[x][y-1]<=size){
next.x = x; next.y = y-1;
found[x][y-1] = true;
//push the newly accessed space to the queue
q.push(next);
//check if there is a fish that can be eaten by the shark
if(space[x][y-1]>0 && space[x][y-1]<size)
//stop bfs
break;
}
//search rightwards
//check if there is a space rightwards & not accessed yet && there is no fish larger than the shark
if(y+1<n && !found[x][y+1] && space[x][y+1]<=size){
next.x = x; next.y = y+1;
found[x][y+1] = true;
//push the newly accessed space to the queue
q.push(next);
//check if there is a fish that can be eaten by the shark
if(space[x][y+1]>0 && space[x][y+1]<size)
//stop bfs
break;
}
//search downwards
//check if there is a space downwards & not accessed yet && there is no fish larger than the shark
if(x+1<n && !found[x+1][y] && space[x+1][y]<=size){
next.x = x+1; next.y = y;
found[x+1][y] = true;
//push the newly accessed space to the queue
q.push(next);
//check if there is a fish that can be eaten by the shark
if(space[x+1][y]>0 && space[x+1][y]<size)
//stop bfs
break;
}
}
//is queue is not empty, a fish was found
if(!q.empty()){
int depth = cur.depth;
//check if there is any other fish within the same distance from the shark
while (!q.empty() && q.front().depth == depth) {
pos temp = q.front(); q.pop();
x = temp.x; y = temp.y;
//check upwards if there is a fish that the shark can eat
// and where its row value is less/equal to than the row value of the fish found before
if (x - 1 >= 0 && space[x - 1][y] > 0 && space[x - 1][y] < size && x - 1 <= next.x) {
//if the new fish found is located on the same row but
//its column value is larger than that of the fish found before, skip this one
if(x-1==next.x && y>next.y)
continue;;
temp.x -= 1; temp.depth++;
next = temp;
}
//check leftwards if there is a fish that the shark can eat
// and where its row value is less/equal to than the row value of the fish found before
if (y - 1 >= 0 && space[x][y - 1] > 0 && space[x][y - 1] < size && x <= next.x) {
//if the new fish found is located on the same row but
//its column value is larger than that of the fish found before, skip this one
if(x==next.x && y-1>next.y)
continue;;
temp.y -= 1; temp.depth++;
next = temp;
}
//check rightwards if there is a fish that the shark can eat
// and where its row value is less/equal to than the row value of the fish found before
if (y + 1 < n && space[x][y + 1] > 0 && space[x][y + 1] < size && x <= next.x) {
//if the new fish found is located on the same row but
//its column value is larger than that of the fish found before, skip this one
if(x==next.x && y+1>next.y)
continue;
temp.y += 1; temp.depth++;
next = temp;
}
//check downwards if there is a fish that the shark can eat
// and where its row value is less/equal to than the row value of the fish found before
if (x + 1 < n && space[x + 1][y] > 0 && space[x + 1][y] < size && x + 1 <= next.x) {
//if the new fish found is located on the same row but
//its column value is larger than that of the fish found before, skip this one
if(x+1==next.x && y>next.y)
continue;
temp.x +=1; temp.depth++;
next = temp;
}
}
//the shark ate the fish
//update the state of the shark and the space
space[next.x][next.y] = 0;
//did the shark get bigger?
exp++;
if(exp==size){
exp = 0; size++;
}
//shark has moved (next.depth) seconds to eat the fish
sec += next.depth;
//new position of the shark
r = next.x; c = next.y;
//the shark has successfully found the fish to eat
return true;
}
//if queue is empty, no fish that can be eaten by the shark was found
return false;
}
};
int main(){
baby_shark babyShark;
int** space;
int n;
int fish;
//get input and initialize the space
cin>>n;
space = new int*[n];
fish = 0;
for(int i=0; i<n; i++){
space[i] = new int[n];
for(int j=0; j<n; j++){
cin >> space[i][j];
//the baby shark was found
if(space[i][j]==9){
//initialize its state
babyShark.initialize(i,j);
space[i][j] = 0;
}
//fish was found
else if(space[i][j]>0)
fish++;
}
}
//repeat the search until the shark finds all fish or it fails to find fish to eat
for(int i=0; i<fish; i++){
if(!babyShark.find_fish(space, n))
break;
}
//print out the result
cout << babyShark.sec;
}
처음에 한 가지 실수했던 점은, 물고기와 상어의 크기가 같을 때도 물고기를 먹는 것으로 코드가 작성되었다는 것이다. 상하좌우로 이동할 때 지나갈 수 있는 칸인지 먼저 확인하고 지나갈 수 있는 칸이라면 그 칸에 물고기가 있는지 확인하는 식으로 했는데, 크기가 더 큰 물고기는 이미 제외했기 때문에 물고기가 있는 칸인지 아닌지만 확인하면 된다고 착각해서 그랬던 것 같다. 이런 문제에서는 조건을 하나씩 따져가면서 이 조건이 코드로 올바르게 구현됐는지 꼼꼼히 살펴보는 수 밖에 없는 것 같다.
두 번째 문제는, bfs 실행 순서가 내가 예상했던 순서가 아니라는 점이다. 예를 들어, 현재 위치에서 같은 거리만큼 떨어져 있는 두 물고기 중에서 한 물고기는 오른쪽 위에 다른 물고기는 왼쪽 아래에 있다면, 상어는 왼쪽 아래 물고기를 먹으러 가게 된다(문제 조건에 따르면 오른쪽 위의 물고기를 먹어야 한다). 그래서 한 번 물고기를 찾으면, bfs를 중단하고 같은 거리만큼 떨어져 있지만 더 위쪽에 있거나 같은 행에 있을 때 왼쪽에 있는 경우를 찾기 위해 queue에서 남은 element들을 체크하도록 코드를 수정했다.
또한, 물고기까지의 거리를 계산할 때 물고기의 좌표와 상어가 위치한 좌표의 차이로 계산했는데, 이 경우 가는 길 중간에 크기가 큰 물고기가 있어서 돌아간 경우를 고려하지 않기 때문에 틀린 방법이다. 따라서 bfs 깊이를 이용하여 계산하였다.
또, 상하좌우를 살펴볼 때,
int dir_x[] = {-1,0,0,1};
int dir_y[] = {0,-1,1,0};
와 같이 전역 변수로 만들어놓고 사용하면 코드도 간결해지고 편하다.
아래는 더 간단하게 작성한 코드
#include <iostream>
#include <queue>
using namespace std;
//up,left,right,down
int dir_x[] = {-1,0,0,1};
int dir_y[] = {0,-1,1,0};
//position
typedef struct pos{
int x; //row
int y; //column
int depth; //depth in the bfs tree
}pos;
//baby shark
class baby_shark{
private:
int r, c; //current position of the shark
int size; //size of the shark
int exp; //size-exp: the amount of fish the shark needs to get bigger
public:
int sec; //the amount of time the shark moved (in seconds)
/**
* initialize the state of the shark
* @param x: row
* @param y: col
*/
void initialize(int x, int y){
r=x; c=y;
size = 2;
exp = sec = 0;
}
/**
* find a fish that can be eaten by the shark
* @param space: 2d int array, tells where fish are
* @param n: size of the space (n*n)
* @return true if fish is found, false if no fish is found
*/
bool find_fish(int** space, int n){
queue<pos> q;
pos cur, next;
bool** found; //true if (i,j) is already accessed
int x,y;
//initialize the array 'found'
found = new bool* [n];
for(int i=0; i<n; i++){
found[i] = new bool[n];
for(int j=0; j<n; j++)
found[i][j] = false;
}
//start from the current location of the shark
cur.x = r; cur.y = c; cur.depth = 0;
q.push(cur);
while(!q.empty()){
cur = q.front(); q.pop();
//look for any fish in the adjacent blocks(up->left->right->down)
for(int i=0; i<4; i++){
//row and column values of the adjacent blocks
x = cur.x+dir_x[i]; y = cur.y+dir_y[i];
//check if the shark can pass by this block
if(0<=x && x<n && 0<=y && y<n && !found[x][y] && space[x][y]<=size){
//the shark can pass by this block, push the block to the queue
found[x][y] = true;
next.depth = cur.depth+1;
next.x = x; next.y = y;
q.push(next);
//check if there is a fish that is smaller than the shark in this block
if(0<space[x][y] && space[x][y]<size){
//check if there is any other fish that is within the same distance
while(!q.empty() && q.front().depth == cur.depth){
pos temp = q.front(); q.pop();
//search in the adjacent blocks(up->left->right->down)
for(int j=0; j<4; j++){
x = temp.x+dir_x[j]; y = temp.y+dir_y[j];
//check if there is a fish that is smaller than the shark
if(0<=x && x<n && 0<=y && y<n && 0<space[x][y] && space[x][y]<size){
//compare (row,col) values of the fish
if((x==next.x && y<next.y) || x<next.x){
next.x = x; next.y = y; next.depth = cur.depth+1;
}
}
}
}
//The shark eats the fish
space[next.x][next.y] = 0;
//The shark is now moved to the new location
r = next.x; c = next.y;
//did the shark get bigger?
if(++exp==size){
exp = 0; size++;
}
//the shark moved (next.depth) seconds to eat the fish
sec +=next.depth;
return true;
}
}
}
}
//no fish available
return false;
}
};
/**
* main function
*/
int main(){
baby_shark babyShark;
int** space; //gives info of the space where the fish and the shark are
int n; //size of the space (n*n)
int fish; //total number of fish
//get the size of the space from user input
cin>>n;
space = new int*[n];
fish = 0;
//get info of the space
for(int i=0; i<n; i++){
space[i] = new int[n];
for(int j=0; j<n; j++){
cin >> space[i][j];
//shark
if(space[i][j]==9){
//initialize the state of the shark
babyShark.initialize(i,j);
space[i][j] = 0;
}
//fish
else if(space[i][j]>0)
fish++;
}
}
//search until there is no fish left that the shark can eat
for(int i=0; i<fish; i++){
if(!babyShark.find_fish(space, n))
break;
}
//print out the result
cout << babyShark.sec;
}