[백준] #16236. 아기 상어

문제는 여기서 확인할 수 있다. BaekJoon #16236. 아기 상어

---

📌 POINT

1. 아기 상어가 먹고 살 수 있는 최대 기한을 구하라

2. 큰 물고기는 먹지도, 지나가지도 못한다.

3. 작은 물고기는 먹을 수 있다.

4. 크기가 같은 물고기는 먹을 수는 없지만 지나갈 수는 있다.

5. 여러 마리를 먹을 수 있다면 그 중 가장 (1) 가까운 (2) 위에 있는 (3) 왼쪽에 있는 걸 순서대로 확인해서 결정한다.

6. 상어 크기와 같은 수의 물고기를 먹으면 크기 + 1

7. 주의할 점

• 같은 크기의 물고기에 대한 조건 확인
• 최단 거리가 같은 물고기 중에서 가장 위, 같은 높이라면 가장 왼쪽에 있는 물고기 선택하기
• 상어 위치 0으로 만들고 상어의 지금 위치를 구조체로 따로 저장하는게 효율적이다. 먹은 자리는 0으로 바꾼다.

---

🚀 풀이

Ready

재귀보다는 while문을 쓰는게 편할 것 같아서 알고리즘을 간략하게 정리해봤다.

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

구현하기 전에 시간 복잡도를 확인해봤다.

• 먹을 수 있는 물고기 확인 O(N^2)
• target 확인 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. Target 물고기 찾기

• 이동 거리가 가장 짧은 물고기
  • 거리가 같다면 가장 위에 있는 물고기
    • 높이가 같다면 가장 왼쪽에 있는 물고기

일단 이동 거리 순이기 때문에 BFS를 사용하여 상어로부터 한칸씩 넓혀가며 target을 찾았다.

이때 같은 크기의 물고기는 먹지 못하고 그냥 지나치는 조건도 포함해야한다.

// 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;
}

주의할 점

• 같은 크기의 물고기 조건
  범위를 체크할 때는 지나가되 이후 target이 아니라 지나가도록 if문을 작성한다.

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

• 최단 거리 내 target 비교

// 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;

---

전체 코드

이번 문제는 알고리즘보다는 구현을 할 수 있느냐의 문제라서 중요한 포인트만 소개했다. 위의 링크를 클릭하면 전체 코드를 확인할 수 있다.