16236번. 아기 상어

 

 

아이디어

먼저 BFS 를 통해 현재 상어의 위치에서 가까운 위치부터 탐색을 진행하며 먹을 수 있는 물고기가 있는지 확인한다.

이 때 자신보다 큰 물고기가 있는 칸은 상어가 통과할 수 없으므로 이 점에 주의해서 BFS 를 수행한다.

 

먹을 수 있는 물고기가 없으면 false 를 반환하고

먹을 수 있는 물고기가 있다면

1. 해당 물고기의 위치로 상어를 이동시키고, 

2. 소요된 시간을 더해주고

3. 먹은 물고기 수를 늘려준 후 

4. 먹은 물고기 수가 상어의 크기와 같다면 상어의 크기를 키워준다.

5. true 를 반환한다.

 

 

위 내용이 false 를 반환할 때까지 반복하면 문제에서 요구하는 답을 얻을 수 있다.

 

 

풀이코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

    static int time = 0;
    static int numOfEat = 0;
    static int sharkSize = 2;
    static int[] position = new int[2];
    static int[][] area;
    static int N;

    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(br.readLine());
        area = new int[N][N];

        for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++) {
                area[i][j] = Integer.parseInt(st.nextToken());
                if (area[i][j] == 9) {
                    position[0] = i;
                    position[1] = j;
                    area[i][j] = 0;
                }
            }
        }

        while (true) {
            if (!eat()) break;
        }

        System.out.println(time);
    }

    public static boolean eat() {
        boolean flag = false;

        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[]{position[0], position[1], 0});

        boolean[][] visited = new boolean[N][N];
        visited[position[0]][position[1]] = true;

        int[] fish = {N, N};
        int distance = N * N;
        while (!queue.isEmpty()) {
            int[] now = queue.poll();

            if (now[2] >= distance) continue;

            for (int i = 0; i < 4; i++) {
                int nx = now[0] + dx[i];
                int ny = now[1] + dy[i];

                if (nx < 0 || ny < 0 || nx >= N || ny >= N || visited[nx][ny]) continue;
                if (area[nx][ny] > sharkSize) continue;

                if (0 < area[nx][ny] && area[nx][ny] < sharkSize) {
                    flag = true;
                    distance = now[2] + 1;
                    if (fish[0] > nx || (fish[0] == nx && fish[1] > ny)) {
                        fish[0] = nx;
                        fish[1] = ny;
                    }
                }

                queue.add(new int[]{nx, ny, now[2] + 1});
                visited[nx][ny] = true;
            }
        }

        if (flag) {
            area[fish[0]][fish[1]] = 0;
            time += distance;
            numOfEat += 1;
            if (numOfEat == sharkSize) {
                sharkSize += 1;
                numOfEat = 0;
            }
            position[0] = fish[0];
            position[1] = fish[1];
        }

        return flag;
    }
}