[BOJ] 16236 아기상어 - Java

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

16236번: 아기 상어

---

1. 문제 요약

1. NxN크기의 map에 물고기 M마리가 있다. map에서 0은 빈 칸, 1~6은 물고기 크기, 9는 아기상어의 위치이다.

2. 아기상어의 초기 크기는 2이며, 1초에 1칸 씩 이동한다.

3. 아기상어는 자기보다 크기가 작은 물고기만 먹을 수 있다.

                                    크기가 같은 물고기는 지나갈 수 있으며

                                    크기가 큰 물고기는 지나갈 수도 없다. (벽이라고 생각)

4. 아기상어는 자기보다 작은 물고기 1마리를 향해 이동한다. 

 - 여러 마리일 경우, 거리가 가장 가까운 물고기를 목표로 한다.

 - 거리가 가장 가까운 물고기 또한 여러 마리일 경우, y가 더 작은 녀석, 같을 경우 x가 더 작은 녀석을 목표로 한다.

 - 가장 가까운 거리란, 지나야하는 칸의 개수가 최솟값일 경우를 의미한다. (bfs) (맨하탄 아님)

5. 자신의 크기와 같은 수의 물고기를 먹으면 아기상어의 크기는 1 증가한다.

 

* 물고기는 이동하지 않는다.

* 더 이상 잡아먹을 물고기가 없으면 종료하며, 몇 초 동안 잡아먹을 수 있는지를 출력한다. 

 

2. 풀이

bfs + 시뮬레이션 문제이다.

낚시왕, 미생물격리와 비슷한 문제이다. 차이가 있다면

map에 Fish객체를 넣어주지 않아도 된다는 것,

PriorityQueue 정렬 기준이 여러 개라는 것,

bfs를 사용했다는 것이다.

 

우선은 Fish 객체를 만들어 y,x(좌표), dist(거리), size(크기)를 저장하였다.

그리고 pq를 사용하기 위해 정렬해줬다. 정렬 기준은 거리 - y - x (오름차순)으로 정렬했다.

여기서 pq는 후보 물고기를 저장하는 우선순위 큐이다. 목표 물고기는 pq의 맨 앞 녀석이 된다.

 

1. 무한 반복을 돌면서

2. PriorityQueue를 초기화 해준다.

3. 목표물고기를 찾는다. => bfs 돌면서 pq에 후보 물고기를 넣어준다.

4. 아기상어가 이동한다.

  - 목표 물고기가 없으면 (pq가 비었다면) 종료한다.

  - 목표 물고기가 있으면 (pq가 차있다면) 해당 좌표로 이동한다.

      => 이전 아기상어 위치는 0으로 초기화, 새로운 위치에 9를 넣어준다.(이건 안해줘도 됨)

      => 목표 물고기 좌표로 이동했다는 것은 잡아 먹은 것이므로 먹은 물고기수+1을 해준다. 

      => 먹은 물고기 수가 아기상어의 크기와 동일하면 먹은 물고기수 0 초기화, 아기상어 크기+1을 해준다. 

      => dist만큼 초가 지난 것이므로(1초에 1칸) 초에 dist를 더해준다.

 

내가 놓친 부분은

1. 먹은 물고기 수가 아기상어 크기와 동일할 때, 아기상어 크기+1만 해주고, 먹은 물고기 수를 0으로 초기화해주지 않아서 답이 조금씩 더 크게 나왔었다.

 

3. 코드

package a22_10_23;

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

public class BOJ_16236_아기상어 {

	static PriorityQueue<Fish> pq;
	static int[][] map;
	static int N, M, sec, cnt, nowDist;
	static Fish shark;
	
	static int[] dy= {-1,1,0,0};
	static int[] dx= {0,0,-1,1};
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = null;
		N= Integer.parseInt(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] = Integer.parseInt(st.nextToken());
				if (map[i][j] == 9) {
					shark = new Fish(i, j, 0, 2);
				}
			}
		} //입력 끝
		
		sec=0;
		solution();
		System.out.println(sec);
	}
	
	static void solution() {
		while(true) {
			pq = new PriorityQueue<> (); //pq 초기화
			//1. 목표물고기 찾기
			bfs();
			
			//2. 상어 이동
			//이동할 곳이 없으면 종료(엄마상어에게 도움 요청)
			if (pq.isEmpty()) break;
			//목표 물고기 좌표로 이동
			Fish cur = pq.poll();
			map[shark.y][shark.x] = 0;
			shark.y=cur.y;
			shark.x=cur.x;
			map[shark.y][shark.x] = 9;
			cnt++; //먹음
			sec += cur.dist; //거리만큼 초가 지남
			if (cnt == shark.size) {
				cnt=0;
				shark.size++;
			}
		}
	}
	
	//조건에 만족하면 pq에 넣어줌
	static void bfs() {
		Queue<Fish> queue = new ArrayDeque<> ();
		boolean[][] visited = new boolean[N][N];
		nowDist= Integer.MAX_VALUE;
		
		queue.offer(new Fish(shark.y, shark.x, 0));
		visited[shark.y][shark.x] = true;
		while (!queue.isEmpty()) {
			Fish cur = queue.poll();
			for (int d=0; d<4; d++) {
				int ny= cur.y+dy[d];
				int nx= cur.x+dx[d];
				if (ny<0 || ny>=N || nx<0 || nx>=N || visited[ny][nx] || map[ny][nx] > shark.size) continue;
				//크기 작거나 같은 물고기들만 남음
				queue.offer(new Fish(ny, nx, cur.dist+1));
				visited[ny][nx] = true;
				
				if (map[ny][nx] != 0 && map[ny][nx] < shark.size) {
					if (cur.dist+1 > nowDist) return; //현재 최대거리보다 크면 pq에 더 안넣어줘도 된다
					pq.offer(new Fish(ny, nx, cur.dist+1));
					nowDist = cur.dist+1;
				}
			}
		}
	}
	
	static class Fish implements Comparable<Fish>{
		int y, x, dist, size;
		Fish(int y, int x, int dist, int size) {
			this.y = y;
			this.x = x;
			this.dist = dist; //거리
			this.size = size;
		}
		Fish(int y, int x, int dist) {
			this.y = y;
			this.x = x;
			this.dist = dist; //거리
		}
		@Override
		public int compareTo(Fish o) { //거리순 - y순 - x순 오름차순
			if (this.dist == o.dist) {
				if (this.y == o.y) {
					return this.x-o.x;
				} else return this.y-o.y;
			} else return this.dist-o.dist;
		}
	}
}