접근
이 문제는 어렵지는 않은데
생각해야할 조건이 많다.
아기상어는 상하좌우로만 이동할 수 있다.
아기상어는 자신의 몸크기보다 작은 물고기만 먹을 수 있다.
그리고 아기상거는 물고기가 없는 곳 ,자신의 몸크기보다 작은 물고기가 있는 곳, 몸크기가 같은 물고기가 있는 곳 이 세곳만 돌아다닐 수 있다.
아기상어는 자신과 가장 가까운 물고기부터 먹는다.
그러나 같은 거리에 존재하는 가장 가까운 물고기가 많다면
높이가 높고 같은 높이이면 더 왼쪽에 존재하는 물고기를 먹으러 이동한다.
아기상어가 자기 몸크기만큼의 물고기를 먹으면 몸크기는 하나 커진다.
만약에 더이상 먹을 물고기가 없으면 끝난다.
따라서 나는 이 문제를 BFS를 통해서 풀었다.
이 문제는 고려할 것이 많기 때문에 함수를 만들어야 한다.
함수
1) 아기상어는 상하좌우로 이동할 수 있지만 그 곳은 0이나 자신의 몸크기보다 작거나 같은 곳만 이동할 수 있다.
static int[] cx = {0,0,1,-1};
static int[] cy = {1,-1,0,0};
.
.
.
for(int j=0;j<4;j++) {
int x = start.x + cx[j];
int y = start.y + cy[j];
if(x>=0 && x<N && y>=0&&y<N && aqua[x][y]<=dolp_size && visit[x][y]==false){
visit[x][y]=true;
Q.offer(new XY(x,y));
}
}//상하좌우 for2) 아기상어가 더 이상 먹을 물고기가 없는지 확인하는 함수
static boolean can_eat(){
int live_fishes=0;
int end=0;
if(dolp_size>6){
end=6;
}else{
end=dolp_size-1;
}
for(int i=1;i<=end;i++){
live_fishes+=fishes[i];
}
if(live_fishes==0) return false;
else return true;
}
내 몸크기보다 작은 물고기의 수를 세는데
더 이상 먹을 물고기가 없으면 false를 반환하는데
여기서 눈여겨 봐야할 것은
내 몸크기가 6보다 큰 경우에도 fishes에 저장된 물고기 수를 세어야 하므로 그 부분을 고려해서 함수를 만든다.
또한 더이상 먹을 물고기가 없으면 BFS를 나가도록 설정했지만
먹을 물고기가 있지만 접근하지 못하는 상황이 있다.
먹을 물고기 주변에 아기상어의 몸크기가 보다 큰 물고기가 있는 경우는 접근하지 못한다.
따라서 BFS를 나가는 경우는
- 더 이상 먹을 물고기가 없거나
- 아기상어가 먹을 수 있는 물고기 주변에 아기상어 몸크기가 보다 큰 물고기가 존재하는 경우이다.
그 이전에 물고기랑 아기상어 위치가 처음에 들어올 때 미리 fishes에 저장한다.
물고기 크기는 1,2,3,4,5,6으로 고정되어 있기 때문에
물고기의 크기가 index가 되어 index크기의 물고기가 들어올 때마다 index의 값을 +1해주는 과정을 넣어준다.
fishes = new int[7];
XY dolp = null;
for(int i=0;i<N;i++){
StringTokenizer st = new StringTokenizer(br.readLine()," ");
for(int j=0;j<N;j++){
aqua[i][j]=Integer.parseInt(st.nextToken());
if(aqua[i][j]==9){
dolp= new XY(i,j);
}else if(aqua[i][j]>0){
fishes[aqua[i][j]]++;
}
}
}3) 가장 가까운 물고기가 여러 마리라면 가장 높은 것, 같은 높이에 여러마리라면 왼쪽에 있는
PriorityQueue<XY> net = new PriorityQueue<>((x1,x2)->{
if(x1.x==x2.x) return x1.y-x2.y;
else return x1.x-x2.x;
});우선순위 큐에 먹을 수 있는 물고기들을 넣는다,
우선순위 큐에 규칙을 넣어준다.
net에 들어오는 물고기는 x가 작은 순으로 저장하고 x가 같다면 y가 작은 순으로 저장한다!
XY는 내가 만든 내부 클래스이다. x,y좌표를 비교해야 하기 때문에 내부 클래스 하나를 만들었다.
static class XY{
int x;
int y;
public XY(int x, int y){
this.x =x;
this.y=y;
}
}전체 풀이
아래와 같다.
import java.util.*;
import java.io.*;
public class Main{
static int[][] aqua;
static int dolp_size = 2;
static int[] cx = {0,0,1,-1};
static int[] cy = {1,-1,0,0};
static boolean[][] visit;
static int eat_fish=0;
static int[] fishes;
static int total_time=0;
static class XY{
int x;
int y;
public XY(int x, int y){
this.x =x;
this.y=y;
}
}
static void BFS(XY dolp, int N,int cnt){
Queue<XY> Q = new LinkedList<>();
Q.offer(dolp);
int time=cnt;
boolean tag = false;
PriorityQueue<XY> net = new PriorityQueue<>((x1,x2)->{
if(x1.x==x2.x) return x1.y-x2.y;
else return x1.x-x2.x;
});
while(!Q.isEmpty()){
int size = Q.size();
for(int i=0;i<size;i++){
XY start = Q.poll();
if(aqua[start.x][start.y]>0&&aqua[start.x][start.y]<dolp_size){
net.offer(new XY(start.x,start.y));
// System.out.println("x:"+start.x+"y:"+start.y);
tag=true;
}
for(int j=0;j<4;j++) {
int x = start.x + cx[j];
int y = start.y + cy[j];
if(x>=0 && x<N && y>=0&&y<N && aqua[x][y]<=dolp_size && visit[x][y]==false){
visit[x][y]=true;
Q.offer(new XY(x,y));
}
}//상하좌우 for
}//Q에 있는거 하나씩 뽑은 for
if(tag==true) break;
time++;
}//비어있는지 while
if(tag==true){
eat_fish++;
if(eat_fish==dolp_size){
dolp_size++;
eat_fish=0;
}
XY die_fish = net.poll();
fishes[ aqua[die_fish.x][die_fish.y]]--;
aqua[die_fish.x][die_fish.y]=0;
for(boolean v[] : visit) Arrays.fill(v,false);
if(can_eat()){
total_time=time;
BFS(new XY(die_fish.x,die_fish.y),N,time);
}else {total_time=time;}
}
}
static boolean can_eat(){
int live_fishes=0;
int end=0;
if(dolp_size>6){
end=6;
}else{
end=dolp_size-1;
}
for(int i=1;i<=end;i++){
live_fishes+=fishes[i];
}
if(live_fishes==0) return false;
else return true;
}
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int N = Integer.parseInt(br.readLine());
aqua = new int[N][N];
visit = new boolean[N][N];
fishes = new int[7];
XY dolp = null;
for(int i=0;i<N;i++){
StringTokenizer st = new StringTokenizer(br.readLine()," ");
for(int j=0;j<N;j++){
aqua[i][j]=Integer.parseInt(st.nextToken());
if(aqua[i][j]==9){
dolp= new XY(i,j);
}else if(aqua[i][j]>0){
fishes[aqua[i][j]]++;
}
}
}
aqua[dolp.x][dolp.y]=0;
BFS(dolp,N,0);
bw.write(Integer.toString(total_time));
bw.flush();
bw.close();
br.close();
}
}