[백준] 16236. 아기 상어 (Java)

16236. 아기 상어

16236번: 아기 상어

---

아이디어💡

1차시도

1. 물고기 크기가 6가지 → 각 크기 별 남아있는 개수,
2. 먹을 수 있는 물고기 개수 세면서 가기 → 먹을수있는게 없으면 끝

일반 멤버 변수

1. 물고기 크기별 물고기 개수 저장: int[]
2. 아기상어 객체 인스턴스
3. 맵
4. 현재 시간
5. 먹을 수 있는 물고기 개수
   1. 초기는 크기 1인 물고기 개수

내부에 아기상어 클래스 생성

멤버 변수

1. 위치
2. 상어 크기
   • 초기값 : 2
3. 먹은 물고기 개수

기능

1. 먹기
2. 해당 위치의 물고기 크기에 대한 물고기 개수 감소 먹은 물고기 개수 증가 먄약 먹은 물고기 개수 == 상어 크기 -> 성장(상어 크기+1, 먹은 물고기 개수 = 0)
3. 이동
4. 상 -> 좌 -> 하 -> 우 순서로 탐색 1. bfs로 먹을 수 있는 게 나올 때까지 탐색 2. 먹을 수 있는게 나오면 break; 3. 해당 위치로 이동, 그리고 그만큼 시간 더하기
5. 먹을 수 있는지 판단
6. 해당 위치의 물고기 크기 확인 -> 더 작으면 true else false

⇒ bfs 뭔가 구현이 어려움. 내 생각과 안됨. → 우선순위 큐로 해볼까

→ 우선순위 큐로 만들기 어려움. 더 큰 상어를 못지나가기 때문에

---

2차 시도

BFS!

멤버 클래스

Position → 좌표

Fish

• 멤버 변수
  • Position position
    • 물고기 좌표
  • boolean isEaten
    • 먹혔는지 여부
• 함수
  • void eaten()
    • 먹히기
    • isEaten ← true;

FishGroup

• List
• 무게에 따른 물고기그룹

BabyShark

• 멤버 변수
  • Position position
    • 아기상어 좌표
  • int size
    • 아기상어 크기
  • int eatCnt
    • 먹은 물고기 수
  • Fish targetFish
    • 먹을 물고기
• 함수
  • void growUp()
    • 성장
    • size++, eatCnt = 0
  • void eat()
    • 현재 위치에 있는 물고기 먹기
      • eatCnt++
      • 지도에서 물고기 없애기
        • arr[position] ← 0
      • 만약 크기만큼 먹었을 경우 → growUp()
    • fish.eaten()실행
  • void move()
    • 타겟 물고기로 이동
      • 상어 위치 업데이트
  • void setTargetFish()
    • 우선순위 큐에 먹을 수 있는 물고기 위치 담기
    • 우선순위에 따라 제일 최우선의 물고기 먹기 → eat()

Main 클래스

• 멤버 변수
  • int[][] arr
    • 지도
  • int N
    • 지도 크기
  • BabyShark babyShark
    • 아기 상어 뚜두루뚜뚜
  • FishGroup[] fishgroups
    • 무게별 물고기 그룹
    • 인덱스가 곧 물고기 크기
• main 함수
  1. 입력 받아서 물고기 그룹 채우기
  2. 아기상어 타겟이 있을 동안
     1. move()
     2. eat()
     3. setTargetFish()

---

시간복잡도⌛

• 먼저, 코드는 아기 상어가 더 이상 먹을 수 있는 물고기가 없을 때까지 아기 상어가 물고기를 찾아 이동하고 먹는 과정을 반복합니다. 이 과정에서 물고기를 찾는 작업은 BFS를 사용하여 진행되고, 이 BFS는 각 셀에 대해 한 번씩만 수행됩니다. 따라서, 이 BFS의 시간 복잡도는 O(N^2)입니다.
• 이 BFS는 아기 상어가 물고기를 먹을 때마다 다시 수행되므로, 최악의 경우 아기 상어가 모든 물고기를 먹어야 할 때의 시간 복잡도는 BFS를 N^2번 수행해야 한다는 것을 의미합니다. 따라서, 최악의 경우의 시간 복잡도는 O((N^2)^2) = O(N^4)가 됩니다.
• 이 BFS는 아기 상어가 물고기를 먹을 때마다 다시 수행되므로, 최악의 경우 아기 상어가 모든 물고기를 먹어야 할 때의 시간 복잡도는 BFS를 N^2번 수행해야 한다는 것을 의미합니다. 따라서, 최악의 경우의 시간 복잡도는 O((N^2)^2) = O(N^4)가 됩니다.

⇒ 위 코드의 시간 복잡도는 최악의 경우 O(N^4), 평균적인 경우는 이보다 훨씬 작을 수 있습니다.

---

소스코드🧑‍💻

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
  static class BabyShark {
    Position position = new Position(); // 아기상어 위치
    int size = 2; // 아기상어 크기 (초기값 2)
    int eatCnt = 0; // 먹은 물고기
    PositionDist target; // 타겟 물고기

    void growUp() { // 성장하기
      this.size++; // 사이즈 증가
      this.eatCnt = 0; // 먹은 물고기 수 초기화
    }
    void eat() { // 물고기 먹기
      target = null; // 타겟 초기화
      arr[this.position.x][this.position.y] = 0; // 해당 칸의 물고기 없애기
      this.eatCnt++; // 먹은 물고기 수 증가
      if(this.eatCnt == this.size) growUp(); // 먹은 수와 상어 크기가 같다면 성장!
    }
    void move2Target() { // 해당 타겟으로 이동
      arr[this.position.x][this.position.y] = 0; // 있던 자리 비우기
      this.position = this.target.position;
      time += this.target.dist; // 시간 업데이트
    }
    void setTarget() {
      Queue<PositionDist> queue = new ArrayDeque<>();
      boolean[][] visited = new boolean[N][N]; // 방문 여부
      queue.add(new PositionDist(this.position, 0)); // 현재 상어 위치
      PositionDist target = new PositionDist(null, Integer.MAX_VALUE);

      while(!queue.isEmpty()) {
        PositionDist pd = queue.poll();

        if(pd.dist > target.dist) continue; // 이미 거리가 더 지났다면, 패스
        // 만약 먹을 수 있다면, 타겟 후보로 선정
        if(arr[pd.position.x][pd.position.y] > 0 && arr[pd.position.x][pd.position.y] < this.size) {
          if(target.dist > pd.dist) { // 거리가 짧다면 교체
            target = pd;
          } else { // =(target.dist == pd.dist) { // 거리가 같다면,
            if(target.position.x > pd.position.x) target = pd; // 더 위에 있으면 교체
            else if(target.position.x == pd.position.x && target.position.y > pd.position.y) target = pd; // 그마저도 같다면, 더 왼쪽에 있으면 교체
          }
          continue;
        }

        for(int i=0; i<dx.length; i++) {
          int cx = pd.position.x + dx[i];
          int cy = pd.position.y + dy[i];
          // 위치 벗어나면 패스
          if(cx < 0 || cx >= N || cy < 0 || cy >= N) continue;
          // 나보다 큰 물고기가 있으면 패스
          if(arr[cx][cy] > this.size) continue;
          // 이미 지나친 곳이면 패스
          if(visited[cx][cy]) continue;
          visited[cx][cy] = true;
          // 새 위치, 기존 거리+1 해서 큐에 삽입
          queue.add(new PositionDist(new Position(cx, cy), pd.dist+1));
        }
      }

      this.target = target;
    }
  }
  static class PositionDist {
    Position position;
    int dist;

    public PositionDist(Position position, int dist) {
      this.position = position;
      this.dist = dist;
    }

  }

  static class Position {
    int x, y;
    public Position() {};

    public Position(int x, int y) {
      this.x = x;
      this.y = y;
    }
  }

  static int[][] arr; // 맵
  static int N; // 맵 크기
  static int time; // 시간
  static int[] dx = {-1,0,1,0}; // 상좌하우 : 상, 좌 일수록 우선순위가 높아서.
  static int[] dy = {0,-1,0,1};
  static BabyShark babyShark = new BabyShark(); // 아기상어
  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    N = Integer.parseInt(br.readLine());
    arr = new int[N][N];

    StringTokenizer st;
    for(int i=0; i<N; i++) { // 맵 채우기
      st = new StringTokenizer(br.readLine());
      for(int j=0; j<N; j++) {
        int element = Integer.parseInt(st.nextToken());
        arr[i][j] = element;

        if(element == 9) { // 아기 상어면, 위치 업데이트
          babyShark.position.x = i;
          babyShark.position.y = j;
        }
      }
    }

    while(true) { // 아기상어가 먹을게 있을 동안
      babyShark.setTarget(); // 타겟 설정
      if(babyShark.target.position == null) break;
      babyShark.move2Target(); // 이동
      babyShark.eat(); // 냠냠
    }

    System.out.println(time);
  }
}