16236 아기상어 - 삼성 sw 역량 기출
N * N 의 공간에 물고기 M 마리와 아기상어 1마리가 있다.
한 칸에 최대 한 마리의 물고기가 존재한다.
처음 아기상어의 크기는 2이고 아기상어가 한 칸씩 이동할 때마다 1초가 지난다.
아기상어는 자기보다 큰 물고기를 지나갈 수 없고, 나머지칸은 지나갈 수 있다.
아기상어와 크기가 같은 물고기는 지나갈 수 있고, 먹을 수는 없다.
아기상어보다 크기가 작은 물고기는 먹을 수 있다.
-
먹을 수 있는 물고기가 1마리라면 그 물고기를 먹으러 간다.
-
먹을 수 있는 물고기가 여러마리이면 가장 가까운 물고기를 먹으러 간다.
- 거리가 같다면 가장 위쪽에 있는 물고기를 먹으러 간다.
- 이런 물고기가 여러마리라면 가장 왼쪽에 있는 물고기를 먹으러 간다.
-
먹을 수 있는 물고기가 없으면 그만둔다.
아기상어는 자기의 크기와 같은 수의 물고기를 먹으면 크기가 커진다.
크기가 2인 아기상어가 물고기를 2마리 먹으면 크기가 3이 된다.
구현
-
BFS를 사용해 먹을 수 있는 물고기를 찾아 좌표와 이동거리를 list에 저장한다.
-
Queue에는 좌표와 이동거리를 저장한다.
-
이동거리는 이전에 뽑은 queue의 이동거리에 1을 더해준다.
-
BFS가 끝나면 list에서 가장 가깝고, 위에 있고, 왼쪽에 있는 물고기를 찾는다.
-
총 소요 시간에 이동 거리를 더해주고, 아기상어의 위치를 먹은 물고기의 위치로 바꾼 후 map을 0으로 바꾼다.
- 아기상어가 먹은 물고기 수가 크기와 같다면 아기상어의 size를 올려준다.
stack으로 선언하여 먹을 때마다 감소하게 구현하였다.stack이 0이면 크기를 증가시키고 stack을 현재 크기로 초기화한다.
-
1~6을 반복하면서 list가 없으면 break
- 총 소요 시간 출력
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main아기상어 {
public static void main(String[] args) throws NumberFormatException, IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
map = new int[N][N];
Shark shark = new Shark();
for(int i = 0; i < N; i++) {
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
for(int j = 0; j < N; j++) {
map[i][j] = Integer.parseInt(st.nextToken());
if(map[i][j] == 9) {
shark.y = i;
shark.x = j;
map[i][j]= 0;
}
}
}
shark.size = 2;
shark.stack = 2;
int time = 0;
while(true) {
boolean[][] visited = new boolean[N][N];
visited[shark.y][shark.x] = true;
Queue<int[]> queue = new LinkedList<>();
queue.add(new int[] {shark.y, shark.x, 0});
List<Fish> fishes = new ArrayList<>();
while(!queue.isEmpty()) {
int[] n = queue.poll();
for(int i = 0; i < 4; i++) {
int yi = n[0]+dy[i];
int xi = n[1]+dx[i];
int move = n[2] + 1;
if(yi >= N || xi >= N || yi < 0 || xi < 0 || visited[yi][xi])continue;
if(map[yi][xi] <= shark.size) {
if(map[yi][xi] > 0 && map[yi][xi] < shark.size) {
fishes.add(new Fish(yi, xi, move));
continue;
}
visited[yi][xi] = true;
queue.add(new int[] {yi,xi,move});
}
}
}
if(fishes.isEmpty()) {
break;
}
Fish fish = fishes.get(0);
for(int i = 1; i < fishes.size(); i++) {
if(fish.dis > fishes.get(i).dis) {
fish = fishes.get(i);
}
else if(fish.dis == fishes.get(i).dis) {
if(fish.y > fishes.get(i).y) {
fish = fishes.get(i);
continue;
}else if(fish.y == fishes.get(i).y) {
if(fish.x > fishes.get(i).x) {
fish = fishes.get(i);
}
}
}
}
time += fish.dis;
shark.y = fish.y;
shark.x = fish.x;
map[shark.y][shark.x] = 0;
shark.stack--;
if(shark.stack==0) {
shark.size++;
shark.stack = shark.size;
}
}
System.out.println(time);
}
static int N;
static int[][] map;
static int[] dy = { -1, 0, 0, 1 };
static int[] dx = { 0, -1, 1, 0 };
}
class Fish {
int y;
int x;
int dis;
Fish(int y, int x, int dis){
this.y = y;
this.x = x;
this.dis = dis;
}
}
class Shark{
int y;
int x;
int size;
int stack;
}