[백준] 16236 아기상어 - JAVA

출처 - 백준 알고리즘

16236번: 아기 상어

---

알고리즘 

• 구현 + BFS 
• 상어 위치에서 가장 가까운 물고기의 위치를 찾기 위해 BFS 로 접근하였다. 
• BFS에 우선순위큐를 사용하여, 거리순 → x좌표 순(가장 위) → y좌표 순(가장 왼)  순으로 큐에 add 하였다. 
• 먹을 수 있는 물고기가 없다면 전체 반복문을 종료
• 먹을 수 있는 물고기가 있다면, 해당 위치로 상어 옮기고 이동 거리만큼 시간 ++ , 물고기 수 ++ 
• 이동한 상어 위치 기준으로, 위 과정 반복

---

 

구현 과정

• map[][] : NxN 크기의 공간 상태 저장 
• time : 아기 상어가 이동하고 있는 시간 
• eat : 아기 상어가 먹은 물고기 수 ( 단, 현재 아기상어의 크기와 같아지면, 아기상어 크기++ , eat=0 해주었다. )
• Point 클래스 : 우선순위큐에 넣을 현재 위치 정보 ( 좌표, 상어로부터의 거리 ) 

 

1. 공간의 상태를 입력받아  map 에 저장하고 map[][]=9 일 경우, 아기 상어의 초기 위치를 기억한다. 

 

2. 더 이상 먹을 수 있는 물고기가 없을 때까지 3~ 과정을 반복한다. 

 

3. 우선순위큐를 사용한 BFS 탐색을 통해 현재 상어 위치에서 먹을 수 있는 물고기 중, 가장 가까운 > 가장 위쪽 > 가장 왼쪽 의 물고기를 찾는다. 

 

4. 만약 먹을 수 있는 물고기가 있다면, 상어의 위치를 해당 물고기의 위치로 이동시키고 이동 거리만큼 time 에 더한다. 상어가 먹은 물고기 수인 eat도 1 증가시킨다. 

 

5. 만약 먹을 수 있는 물고기가 없다면, 반복문을 빠져나와 현재 time을 출력한다. 

 

---

 

소스코드

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

public class Solution_BaekJoon_16236 {
	
	private static int dx[]= {-1,0,1,0};
	private static int dy[]= {0,-1,0,1};
	
	private static int N; 
	/*0:빈칸, 1~6: 물고기 크기, 9:상어위치 */
	private static int[][] map; 
	private static int time=0;
	private static int eat=0; //먹은 물고기 수 
	private static int sx, sy, ssize; //아기상어 위치 ,크기 
	
	static class Point implements Comparable<Point>{
		int x;
		int y;
		int distance;
		
		public Point(int x, int y, int distance) {
			this.x=x;
			this.y=y;
			this.distance=distance;
		}

		@Override
		public int compareTo(Point o) {
			if(this.distance == o.distance) {
				if(this.x==o.x) {
					return this.y-o.y;
				}
				return this.x- o.x;
			}
			return this.distance-o.distance;
		}
	}
    
	public static void main(String[] args) throws Exception {
		BufferedReader br= new BufferedReader(new InputStreamReader(System.in)); 
	
		N=Integer.parseInt(br.readLine()); 
		map= new int[N][N];
		for(int i=0; i<N; i++) {
			String s =br.readLine(); 
			for(int j=0, c=0; j<N; j++, c+=2) {
				map[i][j] = s.charAt(c)-'0';
				if(map[i][j]==9) {
					sx=i; sy=j;
				}
			}
		}
		ssize=2; 
		start(sx, sy); 
		
	}//end of main 
    
	private static void start(int sx, int sy) {
		int sharkx= sx; int sharky=sy; 
		while(true) {
			int dis= eatFish(sharkx, sharky); //물고기를 먹을 수 있는 최소거리 
			//먹은 물고기가 있음  
			if(dis!=-1) {
				map[sharkx][sharky]=0; //상어가 있던 곳은 빈칸으로 
				sharkx= result[0]; sharky=result[1]; //상어 위치 이동 
				time+=dis; 
				eat++; //먹은 물고기 증가 
				
				if(eat==ssize) {
					ssize++;
					eat=0; 
				}
			}
			//먹은 물고기 없음 
			else break; 

		}
		System.out.println(time);
	}
	
	static int result[]= new int[2]; //바뀐 상어의 위치 
	//최소 거리에 있는 먹을 물고기 찾기 - bfs 
	private static int eatFish(int sx, int sy) {
		PriorityQueue<Point> que = new PriorityQueue<>();
		boolean visited[][] = new boolean[N][N];
		que.add(new Point(sx,sy,0)); //현재 상어의 위치 
		visited[sx][sy]= true; 
        
		while(!que.isEmpty()) {
			Point p = que.poll();
			int x= p.x;
			int y= p.y;
			int dist= p.distance;
			//물고기 등장 !! 
			if(map[x][y]>0 && map[x][y] < ssize) {
				map[x][y]=9; //거기로 상어가 이동 
				result[0]=x;
				result[1]=y;
				return dist;
			}
			
			for(int dir=0; dir<4; dir++) {
				int nx= x+dx[dir];
				int ny= y+dy[dir];
				
				//경계밖으로 나가거나, 상어보다 크기가 더 큰 물고기가 있다면, 
				if(isOut(nx, ny)|| visited[nx][ny] || map[nx][ny] > ssize) continue; 
				
				visited[nx][ny]= true;
				que.add(new Point(nx,ny,dist+1));
			}
		}
        
		//먹을 수 있는 물고기 없음 
		return -1;
	}
	// 경계 밖으로 나가는지 
	private static boolean isOut(int x, int y)
	{
		return x<0 || x>=N || y<0 || y>=N;
	}
}//end of class