백준 16236번 : 아기 상어 풀이(Java)

www.acmicpc.net/problem/16236

16236번: 아기 상어

최근에 한 번 풀었던 문제를 사정이 있어 다시 풀게 되었는데, 빠르게 풀어서 기분이 좋다. 이런 구현 문제는 정말 조건을 잘 생각하고 그에 맞춰 구현 가능하면 금방 풀리는 데, 아니면 엄청 오래 걸리는 것 같다.

 

Solution

1. 먼저, 아기 상어의 이동의 종료 조건은 다음과 같다.

- 더 이상 먹을 수 있는 물고기가 없을 때(물고기가 아예 없거나, 남은 물고기가 전부 자신보다 크기가 크거나 같을 때)

2. 먹을 수 있는 물고기가 한 마리 남았으면 걔를 먹으면 된다.

3. 한 마리 이상이라면,

- 1순위 : 가장 가까운 물고기

- 2순위 : 가장 가까운 물고기가 여러 마리면, 가장 위에 있는 물고기

- 3순위 : 가장 가깝고 x 축의 값마저 같은 물고기가 여러 마리면, y 값이 가장 작은 물고기

 

이를 축약하면 결국, 젤 가깝고 젤 위에 있고 젤 왼쪽에 있는 물고기 를 먹는다고 생각하면 된다.

 

3. 가장 가까운 물고기, 즉 최단거리를 구해야 한다. 최단거리를 구하는 문제는 대부분이 BFS 로 풀 수 있다.

4. 주의할 점

- 첫 번째 : 가장 가까운 물고기는 여러 마리 일 수 있다. 위에서도 말한 건데, 즉 처음으로 먹을 수 있는(상어보다 크기가 작은) 물고기를 만났다고 해서, 바로 while 문을 끝내버리면 안된다는 것이다. 물고기를 처음 만났을 때의 거리를 최소 거리로 저장해두고 depth 가 그 최소 거리 이상이 되는 시점에서 끝내버리는 것도 가능하지만, 이 문제의 N은 최대가 20밖에 안되기 때문에 안 그래도 충분히 통과가 된다.

- 두 번째 : 여러 마리를 담았다면, 가장 가까운 물고기가 2마리 이상이라는 뜻이고, 1순위 x, 2순위 y 에 따라 정렬 해야 한다. Java 의 Comparable 인터페이스를 구현하는 방법과 Collections.sort 를 안다면 이는 어렵지 않다.

- 세 번째 : 그렇게 정렬까지 마쳤다면, 한 턴에 먹을 수 있는 물고기는 "한 마리" 임을 꼭 생각해야 한다. 정렬을 했으므로, 먹을 수 있는 물고기들 중에 0번째만 먹어야 한다는 것이다.

- 네 번째 : 물고기를 먹었다면, 해당 물고기가 있던 위치는 더 이상 아무것도 없게 되므로 0 으로 만들어 준다. 또한, 상어가 그 물고기를 먹으러 이동했으므로, 상어를 해당 물고기가 있던 위치 로 이동시켜줘야 한다.

 

이를 모두 숙지했다면 구현이 어렵지 않다.

 

Source Code

import java.io.*;
import java.util.*;

public class Main {
    static BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bufferedWriter = new BufferedWriter(new OutputStreamWriter(System.out));
    static int N, time;
    static int[][] map;
    static Shark shark; // 상어의 정보
    static ArrayList<Fish> fishes; // 현재 남아있는 물고기들
    static int[] dx = {-1,1,0,0};
    static int[] dy = {0,0,-1,1};

    static class Node {
        int x;
        int y;
        int depth; // 상어로부터의 거리

        public Node(int x, int y, int depth) {
            this.x = x;
            this.y = y;
            this.depth = depth;
        }
    }
    static class Fish extends Node implements Comparable<Fish>{
    	// Fish 가 Node 를 상속받게 함으로써, 상어로부터의 거리 또한 가지게 한다.
        int size;

        public Fish(int x, int y, int depth, int size) {
            super(x, y, depth);
            this.size = size;
        }

        @Override
        public int compareTo(Fish o) {
            return this.x==o.x?this.y-o.y : this.x-o.x;
        }
    }

    static class Shark {
        int x;
        int y;
        int size;
        int eatFishCount; // 먹은 물고기 수가 size 가 된 순간, size++ 한 뒤 0으로 만들어줘야 한다.

        public Shark(int x, int y, int size, int eatFishCount) {
            this.x = x;
            this.y = y;
            this.size = size;
            this.eatFishCount = eatFishCount;
        }
    }

    static void input() throws IOException {
        N = Integer.parseInt(bufferedReader.readLine());
        map = new int[N][N];
        fishes = new ArrayList<>();
        for(int i = 0 ; i < N; i++) {
            StringTokenizer st = new StringTokenizer(bufferedReader.readLine());
            for(int j = 0 ; j < N; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
                if(map[i][j] == 9) {
                    shark = new Shark(i,j,2,0); // 초기 사이즈가 2인 아기 상어의 위치를 저장해준다.
                } else if(map[i][j] >= 1 && map[i][j] <= 6) {
                    fishes.add(new Fish(i,j, map[i][j], 0));
                    // 초기 물고기들의 위치와 크기를 저장해준다.
                }
            }
        }
    }

    static boolean bfs(boolean[][] visited) {
        Queue<Node> queue = new LinkedList<>();
        queue.add(new Node(shark.x, shark.y, 0)); 
        // 상어의 위치부터 시작하고, 상어부터 시작하므로 depth 는 0으로 시작한다.
        visited[shark.x][shark.y] = true;
        ArrayList<Fish> canEatFishes = new ArrayList<>();
        while (!queue.isEmpty()) {
            Node node = queue.poll();
            int sx = node.x;
            int sy = node.y;
            int sDepth = node.depth;
            for(int i = 0 ; i < 4; i++) {
                int nx = sx + dx[i];
                int ny = sy + dy[i];
                if(nx < 0 || ny < 0 || nx >= N || ny >= N) continue;
                if(visited[nx][ny]) continue;
                if(map[nx][ny] > 0 && map[nx][ny] != 9) {
                //해당 위치에 물고기가 있다면
                    if(shark.size > map[nx][ny]) { // 상어보다 작은 물고기만 먹을 수 있다.
                        if(canEatFishes.size() == 0) { // 아직 먹을 수 있는 물고기가 하나도 없다면 추가
                            canEatFishes.add(new Fish(nx,ny,sDepth+1, map[nx][ny]));
                        } else if(canEatFishes.get(canEatFishes.size() - 1).depth == sDepth + 1) {
                        	//먹을 수 있는 물고기가 하나 이상일 때, 먹을 수 있는 물고기보다
                            //거리가 먼 물고기는 담지 않게 한다.
                            canEatFishes.add(new Fish(nx,ny,sDepth+1, map[nx][ny]));
                        }

                    } else if(shark.size < map[nx][ny]) { // 상어보다 큰 물고기는 지나갈 수도 없다.
                        continue;
                    }
                    // 여기의 else 에는 자연스레, 상어랑 크기가 같은 물고기는 지나갈 수만 있다는 걸 암시한다.
                }
                visited[nx][ny] = true;
                queue.add(new Node(nx, ny, sDepth+1));
            }
        }
        Collections.sort(canEatFishes);
        // compareTo 메서드에 따라 정렬해준다. 같은 물고기가 여럿일 경우
        // x가 작은 물고기, y가 작은 물고기 순서대로 정렬된다.
        if(canEatFishes.size() == 0) {
            return false;
            // 먹을 수 있는 물고기가 아예 없다면, 반복문을 종료하기 위해 false 를 리턴한다.
        }
        Fish eatFish = canEatFishes.get(0);
        // 이미 정렬됐으므로, 먹을 물고기는 0번째에 있다.
        int idx = 0;
        for(int i = 0 ; i < fishes.size(); i++) {
            Fish fish = fishes.get(i);
            if(fish.x == eatFish.x && fish.y == eatFish.y) {
            	// 물고기들 중에, 먹을 물고기는 제거해줘야 한다.
                idx = i; // 제거될 물고기의 인덱스를 저장해주고
                shark.eatFishCount++; // 상어의 포식 횟수를 늘려준 뒤,
                time += eatFish.depth; // 먹을 물고기까지의 거리만큼의 시간이 흐르고,
                shark.x = eatFish.x;
                shark.y = eatFish.y;
                // 먹을 물고기의 위치로 상어를 이동시킨다
                map[eatFish.x][eatFish.y] = 0;
                // 먹힌 물고기는 사라졌으므로 map 에 0으로 표시해준다.
                break;
            }
        }
        if(shark.eatFishCount == shark.size) {
        	// 포식 횟수가 상어의 크기와 같아진다면
            shark.size++; // 상어의 크기를 늘려주고
            shark.eatFishCount = 0; // 포식 횟수를 초기화 한다.
        }
        fishes.remove(idx);
        // 물고기를 제거한다.
        //System.out.println(eatFish.x + " " + eatFish.y + " 먹음, time : " + time);
        return true;
    }

    static void solve() {
        while (!fishes.isEmpty()) { // 물고기가 아예 없거나
            if(!bfs(new boolean[N][N])) { // 먹을 수 있는 물고기가 없을 때 까지 돌린다.
                break;
            }
        }
        System.out.println(time);
    }

    public static void main(String[] args) throws IOException {
        input();
        solve();
        bufferedReader.close();
        bufferedWriter.close();
    }
}