[백준] 16236번 아기 상어 (C++, JAVA)

16236번: 아기 상어

BFS를 이용하여 상어 크기와 같은 물고기가 있거나 빈칸인 공간으로 이동하면서

상어 크기보다 작은 물고기를 발견하면 우선순위 큐에

BFS의 깊이(걸린 시간), x좌표, y좌표를 넣어준다.

 

탐색을 다 마치고 돌아와

우선순위 큐가 비어있으면 먹을 수 있는 물고기가 없는 것이므로 종료 후 최종 시간 출력,

비어있지 않으면 큐 안에서

1. 깊이(걸린 시간)가 가장 작은 순서대로

2. x좌표가 가장 위에 있는 순서대로

3. y좌표가 가장 왼쪽에 있는 순서대로

오름차순 정렬되어있는 상태이므로

top에 있는 깊이를 최종 시간에 더한 뒤 큐를 모두 비워주고

먹은 물고기의 수를 + 1 해준다.

 

현재 상어의 크기와 먹은 물고기의 수가 같다면

상어의 크기를 + 1 해주고 먹은 물고기의 수는 0으로 리셋 해준 후

이 과정을 반복해준다.

 

< C++ 코드 >

#include <iostream>
#include <queue>
#include <functional>
#include <cstring>
using namespace std;
int N, a, b, res, eat, Size = 2, x, y, d;
int arr[21][21], dx[4] = { -1, 1, 0, 0 }, dy[4] = { 0, 0, -1, 1 };
bool visited[21][21] = { false };
priority_queue <pair<int, pair<int, int>>, vector<pair<int, pair<int, int>>>, greater<pair<int, pair<int,int>>>> pq; //BFS 깊이(초), x좌표, y좌표
queue <pair<int, pair<int, int>>> q;
void Bfs() {
	while (!q.empty()) {
		for (int i = 0; i < 4; i++) {
			x = q.front().second.first + dx[i], y = q.front().second.second + dy[i], d = q.front().first;
			if (x >= 0 && x < N && y >= 0 && y < N && visited[x][y] == false) {
				visited[x][y] = true;
				if (!arr[x][y] || arr[x][y] == Size) q.push(make_pair(d + 1, make_pair(x, y)));
				else if (arr[x][y] < Size) pq.push(make_pair(d + 1, make_pair(x, y)));
			}
		}
		q.pop();
	}
}
int main() {
	cin >> N;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cin >> arr[i][j];
			if (arr[i][j] == 9) a = i, b = j, arr[i][j] = 0;
		}
	}
	while (1) {
		q.push(make_pair(0, make_pair(a, b)));
		visited[a][b] = true, Bfs();
		memset(visited, false, sizeof(visited));
		if (pq.empty()) break;
		else {
			res += pq.top().first;
			a = pq.top().second.first, b = pq.top().second.second;
			arr[a][b] = 0;
			while (!pq.empty()) pq.pop();
		}
		if (++eat == Size) eat = 0, Size++;
	}
	cout << res;
	return 0;
}

 

< JAVA 코드 >

import java.util.Comparator;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Scanner;

public class BOJ_16236_아기상어 {
	private static int N, res = 0;
	private static int arr[][], dx[] = {-1, 1, 0, 0}, dy[] = {0, 0, -1, 1};
	private static int baby[] = {0, 0, 2, 0}; // x, y, 사이즈, 먹은 횟수
	private static boolean visited[][]; // 방문 체크
	private static Queue <int[]> movable = new LinkedList<>(); // x, y, 깊이(시간)
	private static PriorityQueue <int[]> sharks; // x, y, 깊이(시간)
	
	public static void bfs() {
		while(!movable.isEmpty()) {
			int X = movable.peek()[0], Y = movable.peek()[1], depth = movable.poll()[2];
			for(int i = 0; i < 4; i++) {
				int x = X + dx[i], y = Y + dy[i];
				if(x < 0 || x >= N || y < 0 || y >= N || visited[x][y] || arr[x][y] > baby[2]) continue; // 범위를 벗어나거나 이미 방문했거나 자기보다 큰 사이즈의 물고기가 있다면 넘김
				if(arr[x][y] > 0 && arr[x][y] < baby[2]) sharks.offer(new int[] {x, y, depth + 1}); // 먹을 수 있는 물고기 표시
				movable.offer(new int[] {x, y, depth + 1});
				visited[x][y] = true;
			}
			if(sharks.size() > 0 && (movable.isEmpty() || depth != movable.peek()[2])) { // 먹을 수 있는 물고기 후보 다 탐색 했으면
				int x = sharks.peek()[0], y = sharks.peek()[1]; // 먹으러 갈 상어 위치
				baby[0] = x; baby[1] = y; arr[x][y] = 0; // 아기 상어 위치 갱신, 먹은 거 0으로 표시
				if(++baby[3] == baby[2]) { baby[2]++; baby[3] = 0; } // 몸집만큼 잡아 먹었으면 사이즈++, 먹은 횟수 0으로 갱신
				res += sharks.poll()[2]; // 결과값에 걸린 시간 추가
				movable.clear(); sharks.clear(); // 현재 자리에서 다시 처음부터 시작해야 하므로 초기화
				movable.offer(new int[] {x, y, 0});
				visited = new boolean[N][N]; // 방문 배열도 초기화
				visited[x][y] = true;
			}
		}
	}
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt(); arr = new int[N][N]; visited = new boolean[N][N];

		for(int i = 0; i < N; i++) {
			for(int j = 0; j < N; j++) {
				arr[i][j] = sc.nextInt();
				if(arr[i][j] == 9) { 
					baby[0] = i; baby[1] = j; arr[i][j] = 0; visited[i][j] = true;
					movable.offer(new int[] {i, j, 0});
				}
			}
		}
		
		sharks = new PriorityQueue<>(new Comparator<int[]>() { // 행과 열을 오름차순 시키면 최대한 위, 최대한 왼쪽 조건이 만족됨
			@Override
			public int compare(int[] o1, int[] o2) {
				if(o1[0] == o2[0]) return o1[1] - o2[1];
				return o1[0] - o2[0];
			}
		});
		
		bfs();
		
		System.out.println(res);
	}
}