백준_16236_아기상어

[로직 설명]

1. 먹을 것이 있는지 체크해준다. 있다면 True 없다면 False반환 (checkEat 메소드)

    1-1. 먹을 것이 없다면, 지금까지의 시간을 출력하고 끝낸다.

    1-2. 있다면, 2번으로

2. bfs를 통해 거리 탐색을 한다. 이 때, 아기상어의 크기와 같거나 작아야지만 지나칠 수 있다는 조건을 걸어준다.

3. 거리탐색은 크기나 작거나 같아도 지나갈 수 있지만, 먹을 수있는 것은 크기가 작아야만 한다. 따라서, 아기 상어보다 크기가 작은 것들을 찾고 그 중에서 가장 가까운 거리를 minTime 변수에 저장해준다.

4. 가장 가까운 거리들의 먹이가 여러개 있을 수 있으므로, minTime과 같은 거리의 좌표들을 찾아 ArrayList에 담아준다. (이 때, 먹이의 크기가 0이거나 아기상어의 크기와 같은것은 안된다.)

5. compareTo를 이용하여 arraylist를 정렬해준다.(맨 위에 있는 먹이가 가장 앞으로 그 다음 왼쪽에 있는 먹이가 앞으로 -문제 조건 참고)

6.  가장 가까운 곳에 있고 문제의 조건에 만족하는 것은 arraylist의 맨 앞에 올것이어서, 아기상어의 다음좌표(babyY, babyX)를 갱신한다. 

7. 하나의 먹이를 먹었으므로, grow값을 증가시키고, 이 grow의 값과 baby변수(아기상어크기) 값이 같아지면, baby를 1 증가시키며, grow값은 0으로 초기화한다.

8. 마지막으로 다시 먹을 것이 있는지 확인한 뒤, 먹을 것이 있다면 shark()메소드를 실행하여 전체 과정을 반복한다. 없다면, 함수를 종료시킨다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class Main {
    static int N, baby, babyY, babyX, time, grow;
    static int[][] map, cnt;
    static boolean[][] visited;
    static int[] dy = { -1, 0, 1, 0 };
    static int[] dx = { 0, -1, 0, 1 };
 
    public static void main(String[] args) throws IOException {
 
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
 
        N = Integer.parseInt(st.nextToken());
        map = new int[N][N];
 
        babyY = 0;
        babyX = 0;
        for (int i = 0; i < map.length; i++) {
            st = new StringTokenizer(br.readLine());
            if (st.hasMoreTokens()) {
                for (int j = 0; j < map[i].length; j++) {
                    map[i][j] = Integer.parseInt(st.nextToken());
                    if (map[i][j] == 9) {
                        babyY = i;
                        babyX = j;
                    }
                }
            }
        }
        grow = 0;
        baby = 2;
        time = 0;
        shark();
    }
 
    public static void shark() {
        if (checkEat()) {
            bfs(babyY, babyX);
            int minTime = Integer.MAX_VALUE;
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    if (cnt[i][j] != 0 && map[i][j] != 0 && map[i][j] < baby) {
                        if (minTime > cnt[i][j]) {
                            minTime = cnt[i][j];
                        }
                    }
                }
            }
 
            ArrayList<Edge> al = new ArrayList<>();
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    if (cnt[i][j] == minTime && map[i][j] != 0 && map[i][j] != baby) {
                        al.add(new Edge(i, j));
                    }
                }
            }
            if (al.size() == 0) {
                System.out.println(time);
                return;
            }
            Collections.sort(al);
            time += minTime;
            babyY = al.get(0).y;
            babyX = al.get(0).x;
            grow++;
            map[babyY][babyX] = 0;
            if (grow == baby) {
                baby++;
                grow = 0;
            }
 
            if (checkEat()) {
                shark();
            } else {
                System.out.println(time);
                return;
            }
        } else {
            System.out.println(time);
            return;
        }
 
    }
 
    public static boolean checkEat() {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (map[i][j] > 0 && map[i][j] <= baby) {
                    return true;
                }
            }
        }
        return false;
    }
 
    public static void bfs(int y, int x) {
        map[y][x] = 0;
        visited = new boolean[N][N];
        cnt = new int[N][N];
 
        Queue<int[]> que = new LinkedList<>();
        que.offer(new int[] { y, x });
        visited[y][x] = true;
 
        while (!que.isEmpty()) {
            int[] tmp = que.poll();
            int cy = tmp[0];
            int cx = tmp[1];
 
            for (int d = 0; d < 4; d++) {
                int ny = cy + dy[d];
                int nx = cx + dx[d];
 
                if (safe(ny, nx) && !visited[ny][nx] && map[ny][nx] <= baby) {
                    visited[ny][nx] = true;
                    cnt[ny][nx] = cnt[cy][cx] + 1;
                    que.offer(new int[] { ny, nx });
                }
            }
        }
    }
 
    public static class Edge implements Comparable<Edge> {
        int y;
        int x;
 
        public Edge(int y, int x) {
            this.y = y;
            this.x = x;
        }
 
        @Override
        public int compareTo(Edge o) {
            if (this.y > o.y) {
                return 1;
            } else if (this.y == o.y) {
                if (this.x < o.x) {
                    return 1;
                } else {
                    return 0;
                }
            } else {
                return -1;
            }
        }
    }
 
    public static boolean safe(int y, int x) {
        if (y < N && x < N && y >= 0 && x >= 0) {
            return true;
        }
        return false;
    }
}

 

처리해야 할 조건들이 많아 로직이 흔들릴 수 있지만 문제 설명대로 차근히 풀어나가면 어렵지 않은 문제인 것 같다.

필요한 스킬 : BFS, Comparable 인터페이스