BOJ - 16236 아기 상어

16236 아기상어 : https://www.acmicpc.net/problem/16236

---

Problem

---

Solve

현재 상어의 위치에서 부터 가장 가까운 거리의 먹을수 있는 물고기 까지의 이동하며 더 이상 먹을수 있는 물고기가 없을때 까지 반복한다.

BFS를 통해 먹을수 있는 물고기가 있는 경우 좌표정보와 이동 거리를 반환하고 먹을수 있는 물고기가 없는 경우 null을 반환하여 반복문을 멈추도록 구현하였다.

문제 풀이순서는 아래와 같다.

1. 상어의 위치와 크기 초기화.
2. BFS를 통해 상어가 먹을수 있는 물고기 리스트를 저장해두었다가 거리가 가장 가깝고 y값이 작고 x값이 작은 물고기 위치 정보를 반환한다.
   • 현재 상어의 크기보다 작은경우 물고기를 저장할 PQ에 저장한다.
   • 상어의 크기보다 같거나 빈칸이라면 이동할 위치 정보 Queue에 저장한다.
   • 모든 곳을 탐색 완료하였을 때 물고기를 저장한 PQ 중 위의 조건에 맞는 물고기 위치 정보(y,x,distance)를 반환한다.
   • 만약 물고기를 저장한 PQ가 비어있다면 null을 반환한다.
3. 물고기 위치정보를 반환받게된다면 상어의 위치정보를 반환받은 정보로 갱신하고 먹은 물고기 개수를 파악해 상어의 크기를 조절하고 이동한 거리를 갱신해준다.
4. 물고기 위치정보를 null로 반환받게 된다면 더이상 먹을수 있는 물고기가 존재하지 않으므로 저장해둔 이동 거리를 반환한다.

위의 구현에서 물고기 위치 정보를 PQ로 저장했는데 Queue로 저장하고 Queue가 비어있지 않을때 정렬을 수행해도 된다.

---

Code

public class 아기상어 {
	//공간 정보
	static int[][] see;
    //상어 정보(0 : y좌표, 1 : x 좌표, 2 : 크기)
	static int[] shark;
    //공간 크기
	static int N;
	static int[] dy = {-1,0,1,0};
	static int[] dx = {0,-1,0,1};
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		N = Integer.parseInt(br.readLine());

		see = new int[N][N];
		//0 : y, 1 : x , 2 : 크기
		shark = new int[3];

		for(int i=0;i<N;i++){
			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
			for(int j=0;j<N;j++){
				see[i][j] = Integer.parseInt(st.nextToken());
				if(see[i][j] == 9){
					shark[0] = i;
					shark[1] = j;
					shark[2] = 2;
                    //상어의 위치를 나타내는 9는 계산에 필요없으므로 갱신
					see[i][j] = 0;
				}
			}
		}

		int answer = 0;
		Move moveInfo;
		int eatCount = 0;
		while(true){
			int y = shark[0];
			int x = shark[1];
			int size = shark[2];
            //먹을수 있는 가장 가까운 물고기 위치 정보
			moveInfo = hunt(y,x,size);

			//반환받은 물고기 위치 정보가 없다면 반복을 끝낸다.
			if(moveInfo == null) break;

			//물고기를 먹게 되면 공간에서 물고기에 대한 정보 갱신
			see[moveInfo.y][moveInfo.x] = 0;
            //상어 위치 정보 갱신
			shark[0] = moveInfo.y;
			shark[1] = moveInfo.x;
            //상어의 크기만큼 물고기를 먹었다면 상어의 크기 +1
			if(++eatCount == size){
				shark[2] = size+1;
				eatCount=0;
			}
            //상어 총 이동거리
			answer += moveInfo.distance;
		}

		bw.write(String.valueOf(answer));
		bw.flush();
		bw.close();
	}

	//가장 가까운 물고기 위치 정보 찾기
    //BFS
	static Move hunt(int y, int x, int size){
    	//이동할 위치 정보
		Queue<Move> moveQueue = new LinkedList<>();
        //현재 상어의 크기에서 먹을수 있는 물고기 위치 정보
		PriorityQueue<Move> fishPQ = new PriorityQueue<>();

		boolean[][] visit = new boolean[N][N];
		visit[y][x] = true;

		moveQueue.offer(new Move(y,x,0));
        
		while(!moveQueue.isEmpty()){
			Move current = moveQueue.poll();

			for(int i=0;i<4;i++){
				int ny = current.y+dy[i];
				int nx = current.x+dx[i];

				if(ny>=0 && nx>=0 && ny<N && nx<N && !visit[ny][nx] && see[ny][nx] <= size){
                	//상어의 크기보다 작은 물고기가 있다면
					if(see[ny][nx] !=0 && see[ny][nx] < size){
                    	//물고기 위치정보 저장
						fishPQ.offer(new Move(ny,nx,current.distance+1));
					}else{
                    	//상어의 크기와 같거나 빈 공간일 경우 이동할 위치 정보에 저장
						moveQueue.offer(new Move(ny,nx,current.distance+1));
					}
					visit[ny][nx] = true;
				}
			}
		}
        //모든 반복이 종료되었을때 상어의 크기보다 작은 물고기가 있다면 조건에 맞는 물고기를 반환해야한다.
        //현재 fishPQ는 상어의 위치와 가까운 순으로 정렬되어있다.
		if(!fishPQ.isEmpty()) {
			int fishPQSize = fishPQ.size();
			Move current = fishPQ.poll();
			for(int i=1;!fishPQ.isEmpty() && i<fishPQSize;i++){
				Move compareMove = fishPQ.poll();

				//현재 거리보다 다음 거리가 더 크다면 더이상 비교할 필요가 없다.
				if(current.distance < compareMove.distance) break;
                //거리가 동일할때 보다 위쪽에 위치한 물고기를 반환하기 위해 current에 더 위쪽에 있는 물고기로 갱신
				if(current.y>compareMove.y) current = compareMove;
                //같은 y축에 있다면 보다 왼쪽에 위치한 물고기를 반환하기 위해 더 왼쪽에 있는 물고기로 갱신
				else if(current.y == compareMove.y){
					if(current.x > compareMove.x) current = compareMove;
				}
			}
			return current;
		}else{
			return null;
		}
	}

	static class Move implements Comparable<Move>{
		int y;
		int x;
		int distance;
		public Move(int y, int x, int distance){
			this.y = y;
			this.x = x;
			this.distance = distance;
		}

		@Override
		public int compareTo(Move o){
			return this.distance - o.distance;
		}
	}
}

---

Result

---

Reference