문제
해결방법
-
현재 아기상어의 위치에서 가장 가까운 먹이를 찾는 BFS를 계속 반복한다. 먹이를 먹은 위치를 다음 BFS의 시작점으로 한다. 더이상 먹을 수 있는 먹이가 없으면 BFS를 중단한다.
-
아기 상어의 초기 크기는 2이고, 아기 상어가 크기 만큼 물고기를 먹으면 그때 크기가 1 증가한다.
-
먹이의 선택 시 가장 위에 있고, 그 중 가장 왼쪽인 물고기를 선택하기 위해 BFS 시 가장 가까운 먹이를 찾아도 중단하지 않고 같은 범위의 다른 먹을 수 있는 물고기를 모두 찾아 우선순위 큐에 넣고 우선순위 큐를 활용해 조건에 맞는 먹이를 찾는다.
동작과정
- BFS를 반복해서 수행한다. 이 때 더이상 먹을 물고기를 찾을 수 없어 false를 리턴하면 종료한다.
- 현재 아기상어의 위치에서 BFS를 시작한다.
- BFS를 돌며 먹을 수 있는 물고기를 찾으면 해당 단계까지만 모두 수행하며 같은 거리의 먹을 수 있는 물고기를 모두 찾아 우선순위 큐에 넣는다.
- 물고기를 먹으면
sizeCount를 증가시키고sizeCount가 아기상어의 크기인size에 도달하면size를 증가시키고sizeCount를 다시 0으로 초기화 시킨다. - 다음 아기 상어의 위치를 먹은 물고기의 위치로 바꾸고 시간을 추가해준다.
코드
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayDeque;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
private static class Point {
int y;
int x;
public Point(int y, int x) {
this.y = y;
this.x = x;
}
}
// 4 방향 탐색을 위한 D
private final static int[][] D = { { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 } };
private static int size, sizeCount, N, time;
// 현재 상어의 위치
private static Point shark;
public static void main(String[] args) throws IOException {
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));
N = Integer.parseInt(in.readLine());
// map을 입력받고 현재 상어의 위치를 저장해둔뒤 map에는 0으로 표시한다.
int[][] map = new int[N][N];
for (int i = 0; i < N; i++) {
StringTokenizer st = new StringTokenizer(in.readLine());
for (int j = 0; j < N; j++) {
map[i][j] = Integer.parseInt(st.nextToken());
if (map[i][j] == 9) {
shark = new Point(i, j);
map[i][j] = 0;
}
}
}
// 초기값을 설정한다 size는 아기상어의 크기, sizeCount는 상어가 먹은 물고기의 개수 (size만큼 먹으면 초기화한다), time은 아기 상어가 활동한 시간
size = 2;
sizeCount = 0;
time = 0;
// 아기상어가 먹이를 먹으면 계속 반복한다.
while (BFS(map));
out.write(time + "");
out.flush();
}
private static boolean BFS(int[][] map) {
// BFS를 위해 위치 좌표들을 저장할 큐, 현재 상어의 위치 부터 시작한다.
Queue<Point> q = new ArrayDeque<>();
q.offer(shark);
// 먹은 물고기와의 거리를 저장하게 될 result, 먹은 물고기가 없다면 Integer.MAX_VALUE를 가지고 있을 것이다.
int result = Integer.MAX_VALUE;
// 현재 BFS 단계를 저장할 step
int step = 0;
// 방문체크, 현재 아기상어의 위치를 방문체크 해준다.
boolean[][] visited = new boolean[N][N];
visited[shark.y][shark.x] = true;
// 도달한 거리가 최소인 모든 물고기들 중 가장 위에 있고 그중 또 가장 왼쪽에 있는 물고기를 선택하기 위한 우선순위 큐
PriorityQueue<Point> foods = new PriorityQueue<>((o1, o2) -> {
if (o1.y == o2.y)
return o1.x - o2.x;
else
return o1.y - o2.y;
});
// 전체 반복문 실행
while (!q.isEmpty()) {
// 현재 큐 사이즈 만큼 반복해서 실행
int qSize = q.size();
while (qSize-- > 0) {
Point now = q.poll();
// 4방향으로 탐색
for (int d = 0; d < 4; d++) {
int ny = now.y + D[d][0];
int nx = now.x + D[d][1];
// 범위 안이고 방문하지 않았다면
if (isInBound(ny, nx, N) && !visited[ny][nx]) {
// 물고기가 아기상어와 같은 크기거나 비어있는 곳이면 지나갈 수 있으므로 방문체크를 하고 큐에 추가해줌
if (map[ny][nx] == size || map[ny][nx] == 0) {
visited[ny][nx] = true;
q.offer(new Point(ny, nx));
}
// 먹을 수 있는 물고기가 있다면 현재의 step에 1을 더한 값이 먹을 수 있는 물고기와의 최솟값이라고 저장해두고 먹이를 저장하는 우선순위 큐에 추가한다.
else if (map[ny][nx] < size) {
result = step + 1;
foods.offer(new Point(ny, nx));
}
}
}
}
// BFS를 다음 단계, 만약 이미 먹이를 찾아서 더이상 할 필요가 없으면 break
step++;
if (step >= result - 1)
break;
}
// 먹이를 못 찾았을 경우
if (result == Integer.MAX_VALUE)
return false;
// 먹이를 찾았을 경우
else {
// sizeCount를 늘려주고, size만큼 아기상어가 먹었으면 아기상어의 size를 증가시켜주고 sizeCount를 초기화
sizeCount++;
if(sizeCount == size) {
size++;
sizeCount = 0;
}
// 현재 아기상어 위치를 먹은 물고기의 위치로 변경해주고 map에는 0 으로 표시해준다.
shark = foods.poll();
map[shark.y][shark.x] = 0;
// 이번 BFS에서 먹은 물고기까지의 시간을 총 시간에 더해준다.
time += result;
return true;
}
}
// 범위 체크
private static boolean isInBound(int y, int x, int N) {
return (y >= 0 && y < N && x >= 0 && x < N);
}
}
성장 중