[伯俊]#16236小さなサメ

問題はここで確認できます.BaekJoon #16236. 小さなサメ

📌 POINT

サメが食べられる最大の期限を求めます.

大きな魚は食べられない

魚は食べられます.

同じ大きさの魚は食べられませんが、行ってもいいです.

何匹か食べられるなら、その中で一番(1)近い(2)の上(3)左側に順番に決めます.

サメと同じ大きさの魚を食べる場合、大きさ+1

注意事項

等サイズの魚の条件確認

最短距離は同じ魚の中で一番上、同じ高さなら一番左の魚

を選びます

サメの位置を0とし,サメの現在位置を構造体として保存することが有効である.食べる席をゼロに変える.

🚀 に答える

Ready

再帰よりwhile文の方が便利なのでアルゴリズムを簡単に整理しました.

while(true) {
	상어 크기 대비 eatable fish count
	if (eatable == 0) 리턴
	else {
			1. 조건에 성립하는 물고기 target 정하기
			2. target 먹기 + 이동
			3. 상어 크기 업데이트
	}
}

実施前に時間的複雑さを確認した.

で食べられる魚を確認O(N^2)

目標確認O(N^2)

食べられる最大魚=whileゲート最大回数(N^2-1)

したがって,時間的複雑度はO(N*N−1)*(N*N)=O(N^4)である.
しかしNはせいぜい20であり,与えられた時間も2秒あるので,直接実現しても問題ない.

Go

1.全体アルゴリズム

上はReadyで紹介したようにコードで実現しました.

int baby_shark(int n, position shark){
    int count_day = 0;
    int shark_size = 2;
    int count_eat = 0;
    while(true){
        // count eatable fishes
        int eatable_fish = count_eatable_fish(n, shark_size);
        
        // call mom
        if(eatable_fish == 0)
            return count_day;
        else {
            // find fish
            fish target = find_target(n, shark, shark_size);
            if(target.shortest_path < 0)
                return count_day;

            // move & eat
            count_day += target.shortest_path;
            shark = target.pos;
            count_eat ++;
            ocean[shark.x][shark.y] = 0;
            
            // size update  
            if(count_eat == shark_size){
                count_eat = 0;
                shark_size ++;
            }
        }
    }
}

2.目的の魚を探す

移動距離が最も短い魚

距離が等しければ一番上の魚

の高さが等しい場合、一番左の魚

まず移動距離なので、BFSを使ってサメからひとつひとつ拡大し、ターゲットを探します.
この場合、同じ大きさの魚は食べられず、通りかかった条件も含めなければなりません.

// with bfs
fish find_target(int n, position shark, int shark_size){
    bool visit[25][25] = {false,};
    int distance = 0;
    queue<position> q;
    // 가장 위, 가장 왼쪽에 있는 물고기를 찾는다.
    fish target(position(25, 25), -1);

    q.push(shark);
    visit[shark.x][shark.y] = true;

    while(!q.empty()){
        int size = q.size();
        distance++;
        for(int i=0; i<size; i++){
            int x = q.front().x;
            int y = q.front().y;
            q.pop();

            for(int i=0; i<4; i++){
                int nx = x + mx[i];
                int ny = y + my[i];
                if(!check_range(n, shark_size, nx, ny)) continue;
                if(visit[nx][ny]) continue;
                visit[nx][ny] = true;
                if(ocean[nx][ny] == 0 || ocean[nx][ny] == shark_size){
                    q.push(position(nx, ny));
                } else {
                    // target
                    if(target.pos.x > nx) 
                        target = fish(position(nx, ny), distance);
                    else if(target.pos.x == nx && target.pos.y > ny) 
                        target = fish(position(nx, ny), distance);
                }
            }
        }
        if(target.shortest_path != -1) return target;
    }
    return target;
}

注意事項

等の大きさの魚の条件
範囲をチェックするときはif文を記入し、後のtargetではなく過去にします.

if(ocean[nx][ny] == 0 || ocean[nx][ny] == shark_size){
    q.push(position(nx, ny));
}

最短距離内目標比較

// target
if(target.pos.x > nx) 
    target = fish(position(nx, ny), distance);
else if(target.pos.x == nx && target.pos.y > ny) 
    target = fish(position(nx, ny), distance);

サメが通っているところ

// move & eat
count_day += target.shortest_path;
shark = target.pos;
count_eat ++;
ocean[shark.x][shark.y] = 0;

完全的コード

今回の問題はアルゴリズムではなく実現できるかどうかですので、重要な点だけを紹介しました.上のリンクをクリックすると、コード全体を表示できます.