문제
N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다.
아기 상어와 물고기는 모두 크기를 가지고 있고, 이 크기는 자연수이다. 가장 처음에 아기 상어의 크기는 2이고, 아기 상어는 1초에 상하좌우로 인접한 한 칸씩 이동한다.
아기 상어는 자신의 크기보다 큰 물고기가 있는 칸은 지나갈 수 없고, 나머지 칸은 모두 지나갈 수 있다. 아기 상어는 자신의 크기보다 작은 물고기만 먹을 수 있다. 따라서, 크기가 같은 물고기는 먹을 수 없지만, 그 물고기가 있는 칸은 지나갈 수 있다.
아기 상어가 어디로 이동할지 결정하는 방법은 아래와 같다.
- 더 이상 먹을 수 있는 물고기가 공간에 없다면 아기 상어는 엄마 상어에게 도움을 요청한다.
- 먹을 수 있는 물고기가 1마리라면, 그 물고기를 먹으러 간다.
- 먹을 수 있는 물고기가 1마리보다 많다면, 거리가 가장 가까운 물고기를 먹으러 간다.
- 거리는 아기 상어가 있는 칸에서 물고기가 있는 칸으로 이동할 때, 지나야하는 칸의 개수의 최솟값이다.
- 거리가 가까운 물고기가 많다면, 가장 위에 있는 물고기, 그러한 물고기가 여러마리라면, 가장 왼쪽에 있는 물고기를 먹는다.
- 아기 상어의 이동은 1초 걸리고, 물고기를 먹는데 걸리는 시간은 없다고 가정한다. 즉, 아기 상어가 먹을 수 있는 물고기가 있는 칸으로 이동했다면, 이동과 동시에 물고기를 먹는다. 물고기를 먹으면, 그 칸은 빈 칸이 된다.
아기 상어는 자신의 크기와 같은 수의 물고기를 먹을 때 마다 크기가 1 증가한다. 예를 들어, 크기가 2인 아기 상어는 물고기를 2마리 먹으면 크기가 3이 된다.
공간의 상태가 주어졌을 때, 아기 상어가 몇 초 동안 엄마 상어에게 도움을 요청하지 않고 물고기를 잡아먹을 수 있는지 구하는 프로그램을 작성하시오.
입력
첫째 줄에 공간의 크기 N(2 ≤ N ≤ 20)이 주어진다.
둘째 줄부터 N개의 줄에 공간의 상태가 주어진다. 공간의 상태는 0, 1, 2, 3, 4, 5, 6, 9로 이루어져 있고, 아래와 같은 의미를 가진다.
- 0: 빈 칸
- 1, 2, 3, 4, 5, 6: 칸에 있는 물고기의 크기
- 9: 아기 상어의 위치
아기 상어는 공간에 한 마리 있다.
출력
첫째 줄에 아기 상어가 엄마 상어에게 도움을 요청하지 않고 물고기를 잡아먹을 수 있는 시간을 출력한다.
접근 방법
-
문제의 요구사항을 분석해보니 구현, 시뮬레이션에 가까운 BFS의 느낌이 옵니다. 하지만 우리가 쉽게 풀던 BFS 유형이 아닌 상어가 먹을 수 있을 때 까지 지나온 거리를 마음껏 누빌 수 있습니다.
-
생각을 조금 전환해 봅시다. 우리는 그때 그때 최단거리에 있는 먹이를 찾아내어 먹으면 됩니다! 즉, BFS 탐색은 먹이를 찾을 때만 진행하고 나머지를 시뮬레이팅하게끔 구조를 바꿔 생각하는겁니다.
-
만일, 지나갈 수 있는 모든 공간을 탐색하고 나서도 먹을 수 있는 (eatable 우선순위 큐)한 먹이가 없다면 그때 우리는 지나간 시간을 0 으로 반환하면 됩니다.
-
반대로 먹을 수 있는 먹이가 있다면? 그 때 먹이를 먹고 해당 지점으로부터 갈 수 있는 가장 가까운 먹이를 찾아서 eat() 을 실행하고 현재 시각에서 먹이를 먹을때까지 걸린 시간을 더해 반환합니다.
⚠️주의할 점⚠️
- 동일 시각에 먹을 수 있는 먹이가 1개 이상 존재할 경우 임의로 선택하게 되면 결과값이 다를 수 있습니다. 때문에 우선순위 큐를 사용해서 가장 위, 왼쪽에 있는 먹이를 먹게끔 고려해야 합니다.
- 상어는 먹을 수 있는 개체가 아닙니다! 입력값을 받을 때 9 (상어의 위치)는 따로 위치만 저장을 해준 뒤 board 에는 넣지 않아야 합니다.
소스 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.PriorityQueue;
public class BabyShark {
static int[] dx = new int[]{-1, 0, 1, 0};
static int[] dy = new int[]{0, 1, 0, -1};
static int n;
static int[][] board;
static int sharkSize = 2, sharkEat = 0;
static class Shark implements Comparable<Shark>{
int x;
int y;
public Shark(int x, int y) {
this.x = x;
this.y = y;
}
@Override
public int compareTo(Shark o) {
if (this.x == o.x) {
return this.y - o.y;
}
return this.x - o.x;
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
n = Integer.parseInt(br.readLine());
board = new int[n][n];
int start_x = 0, start_y = 0;
for (int i = 0; i < n; i++) {
String[] input = br.readLine().split(" ");
for (int j = 0; j < n; j++) {
int cur = Integer.parseInt(input[j]);
if (cur == 9) {
start_x = i;
start_y = j;
continue;
}
board[i][j] = cur;
}
}
System.out.println(eat(start_x, start_y));
}
public static int eat(int x, int y) {
boolean[][] visit = new boolean[n][n];
ArrayDeque<Shark> dq = new ArrayDeque<>();
PriorityQueue<Shark> eatable = new PriorityQueue<>();
int time = 0;
dq.offerLast(new Shark(x, y));
while (!dq.isEmpty() && eatable.isEmpty()) {
time++;
int size = dq.size();
for (int i = 0; i < size; i++) {
Shark now = dq.removeFirst();
for (int j = 0; j < 4; j++) {
int tmpx = now.x + dx[j];
int tmpy = now.y + dy[j];
if (0 <= tmpx && tmpx < n && 0 <= tmpy && tmpy < n && !visit[tmpx][tmpy] && board[tmpx][tmpy] <= sharkSize) {
Shark next = new Shark(tmpx, tmpy);
if (board[tmpx][tmpy] < sharkSize && board[tmpx][tmpy] != 0) {
eatable.offer(next);
}
dq.offerLast(next);
visit[tmpx][tmpy] = true;
}
}
}
}
if (eatable.isEmpty()) return 0;
Shark eatPoint = eatable.poll();
board[eatPoint.x][eatPoint.y] = 0;
sharkEat++;
if (sharkEat == sharkSize) {
sharkEat = 0;
sharkSize++;
}
return eat(eatPoint.x, eatPoint.y) + time;
}
}결과
