아기 상어 [백준 16236][JAVA][골드 5][BFS][시뮬레이션][PQ]

 

[광고 누르면 오늘의 행운 상승!!]

https://www.acmicpc.net/problem/16236

16236번: 아기 상어

BFS 시뮬레이션 문제

Priority Queue와 Queue를 따로 사용하여 
Queue는 일반 이동을 저장하게 하였고
PriorityQueue는 물고기를 먹은 요소를 저장하게 하였다.

1. Class Shark가 좌표, 이동거리, 먹은물고기 수, 몸사이즈를 저장한다.

2. pq는 위를 기준으로 정렬하며 높이가 같을 시 왼쪽 요소로 정렬한다.

3. q를 q.size()만큼 돌아서 한 사이클마다 관리한다 -> 1칸씩 이동할 때 먹은 물고기들을 관리하기 위함

4. 이동할 공간에 물고기가 있다면 pq에 넣는다.

5. pq는 정렬을 마친 가장 앞의 요소를 꺼낸다(가장 가까운 물고기) + q와 pq를 비워준다(다시 시작하기 위함)

6. 물고기를 먹은 갯수와 자신의 사이즈가 같다면 사이즈 업

7. 이동수를 저장한다.

8.반복

 

package Study3;

import java.io.*;
import java.util.*;

class Shark implements Comparable<Shark>{
   int row, col, cnt, size, eat;
   public Shark(int row, int col , int cnt, int eat, int size) {
      this.row = row;
      this.cnt = cnt;
      this.col = col;
      this.eat = eat;
      this.size = size;
   }
   @Override
   public int compareTo(Shark o) {
      if(this.row == o.row) {
         return Integer.compare(this.col, o.col);
      }
      return Integer.compare(this.row, o.row);
   }
   
}
public class 아기상어 {
   static int[] dx = {-1,0,1,0};
   static int[] dy = {0,1,0,-1};
   static int[][] map;
   static boolean[][] visit;
   static int N,ans;
   static Queue<Shark> q = new LinkedList<>();
   static PriorityQueue<Shark> pq = new PriorityQueue<>();
   
   public static void main(String[] args) throws Exception {
	  System.setIn(new FileInputStream("test.txt"));
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      StringTokenizer st = new StringTokenizer(br.readLine());
      
      N = Integer.parseInt(st.nextToken());
      
      map = new int[N][N];
      visit = new boolean[N][N];
      
      for (int i = 0; i < N; i++) {
         st = new StringTokenizer(br.readLine());
         for (int j = 0; j < N; j++) {
            map[i][j] = Integer.parseInt(st.nextToken());
            //물고기 위치
            if(map[i][j] == 9) {
               map[i][j] = 0;
               visit[i][j] = true;
               q.add(new Shark(i,j,0,0,2));
            }
         }
      }
      bfs();
      System.out.println(ans);
      
      
   }
   private static void bfs() {
      
      while(!q.isEmpty()) {
         
         if(pq.size() > 0) {
            Shark shark = pq.poll();
            //맵 변경
            map[shark.row][shark.col] = 0;
            //q, pq를 비워준다(새로 시작)
            pq.clear();
            q.clear();
            visit = new boolean[N][N];
            //먹은 물고기가 자신의 사이즈와 같은 경우 사이즈 업
            if(shark.eat == shark.size) {
               shark.size = shark.size + 1;
               shark.eat = 0;
            }
            //물고기를 먹은 시점 = 물고기를 먹기까지 이동한 횟수
            ans = shark.cnt;
            //bfs재시작
            q.add(new Shark(shark.row,shark.col,shark.cnt,shark.eat,shark.size));
         }
         
         //q 사이즈만큼 돌아야 한다 - 한사이클의 q를 관리해야 하기 떄문
         int size = q.size();
         
         for (int i = 0; i < size; i++) {
            Shark shark = q.poll();
            for (int j = 0; j < 4; j++) {
               int nx = shark.row + dx[j];
               int ny = shark.col + dy[j];
               //맵을 벗어나면 continue;
               if(nx<0 || nx >= N || ny<0 || ny>=N) continue;
               //방문했거나 자신보다 큰 사이즈의 고기가 있으면 continue
               if(visit[nx][ny] || (map[nx][ny] > shark.size)) continue;
               //고기가 있는데 자신보다 작다
               if(map[nx][ny] > 0 && map[nx][ny] < shark.size) {
                  //우선순의 큐에 넣는다(잡은 물고기)
                  pq.add(new Shark(nx,ny,shark.cnt+1,shark.eat+1,shark.size));
               }
               visit[nx][ny] = true;
               q.add(new Shark(nx,ny,shark.cnt+1,shark.eat,shark.size));
            }
         }
      }
   }

}