[알고리즘] 백준16236 아기상어 - 자바

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

16236번: 아기 상어

 

 

[풀이 코드]

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;

public class BOJ_16236_아기상어 {
	static int N, ans, eatCnt;
	static int sharkSize = 2;
	static int[][] map;
	static Queue<Point> q = new LinkedList<>();
	final static int[] dy= {-1, 1, 0, 0};
	final static int[] dx = {0, 0, -1, 1};
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		
		N = parse(br.readLine());
		
		map = new int[N][N];
		for(int i=0; i<N; i++) {
			st = new StringTokenizer(br.readLine());
			for(int j=0; j<N; j++) {
				map[i][j] = parse(st.nextToken());
				if(map[i][j] == 9) {
					q.offer(new Point(i, j));
					map[i][j] = 0;
				}
			}
		}
		
		while(sharkFine());
		System.out.println(ans);
	}
	
	
	private static boolean sharkFine() {
		boolean[][] visited = new boolean[N][N];
		PriorityQueue<Point> pq = new PriorityQueue<>();
		
		int dist = 0;
		
		while(!q.isEmpty()) {
			int size = q.size();
			for(int s=0; s<size; s++) {
				Point point = q.poll();
				
				for(int d=0; d<4; d++) {
					int y = point.y + dy[d];
					int x = point.x + dx[d];
					if(y>=0 && x>=0 && y<N && x<N && !visited[y][x]) {//범위체크
						if(sharkSize > map[y][x] && map[y][x] != 0) { // 아기상어가 더 크면
							pq.offer(new Point(y, x));
						}
						if(sharkSize >= map[y][x]) { // 아기상어가 지나갈 수 있다면 
							q.offer(new Point(y, x));
						}
						visited[y][x] = true;
					}
				}
			}
			
			dist++;
			
			if(!pq.isEmpty()) {
				q = new LinkedList<>(); // 한마리라도 잡히면 초기화
				Point fish = pq.poll();
				map[fish.y][fish.x] = 0;
				q.offer(fish);
				pq = new PriorityQueue<>(); // 한 마리 뻇으니까 초기화
				ans+=dist; // 거리 누적
				
				if(sharkSize == ++eatCnt) {
					sharkSize++;
					eatCnt=0;
				}
				return true;
			}
			
		}
		
		return false;
	}


	private static int parse(String str) {
		return Integer.parseInt(str);
	}

	private static class Point implements Comparable<Point>{
		int y, x;
		Point(int y, int x){
			this.y = y;
			this.x = x;
		}
		@Override
		public int compareTo(Point o) {
			if(this.y == o.y) {
				return this.x-o.x;
			}
			return this.y-o.y;
		}
	}
	
	
}

[풀이 로직]

• ans : 출력해야 할 거리 값
• eatCnt : 물고기를 먹을 때마다 +1
• 큐는 두개를 선언했는데 static으로 선언한 큐는 아기 상어가 이동 가능한 공간을 담을 용도, shakeFind라는 함수 내에 선언된 우선순위 큐는 문제의  '거리가 가까운 물고기가 많다면, 가장 위에 있는 물고기, 그러한 물고기가 여러마리라면, 가장 왼쪽에 있는 물고기를 먹는다.'  조건을 위해 선언해주었다. 이떄 Point 클래스 내에 comparable을 구현해주어야 한다.

1. shakeFind함수를 while문으로 계속 반복하는데 물고기를 한 마리도 잡지 못하는 경우 false가 반환되어 반목 문이 종료된다.
2. shakeFind함수 내에 while문에서 size만큼 for문을 돌게끔했는데 이는 물고기를 잡기까지의 거리를 구하기 위함이다.
   2-1. 만약, 아기상어가 물고기를 한 마리라도 먹게 되면 물고기를 한 마리만 우선순위 큐에서 뺸뒤 다음 첫 시작을 위해 큐에 넣어준다.
   2-2. 문제에서 제시된대로 아기 상어의 크기가 지금까지 먹은 물고기의 개수와 같으면 아기 상어의 크기를 올려주고 먹은 물고기의 수를 초기화해준다.