BJ G5 16236 아기상어

BJ G5 16236 아기상어

 

 

문제링크

http://https://www.acmicpc.net/problem/16236

16236번: 아기 상어

* 일단 문제를 정독 하고 1시간 이상 반드시 고민이 필요합니다.

 

핵심 컨셉

고려사항

 * 아기상어의 크기와 성장
 -- 아기 상어와 물고기는 모두 자연수에 해당하는 크기를 가지고 있다. 
 -- 아기상어의 초기 크기는2이고 자기 크기와 같은 수의 물고기를 먹었을 때 크기가 1 증가.
 -- 이때 주의 사항은 자신의 크기 만큼이 아니라 크기와 같은 수이다. 즉 사이즈가 3인 상어는 3번 물고기를 먹으면 4가된다.

  * 아기상어의 동작
  -- 자신보다 작은 물고기가 있는 곳으로 이동 가능, 먹을수 있음
  -- 자신과 같은 크기의 물고기가 있는 곳으로 이동 가능, 먹을 수는 없음
  -- 자신보다 큰 물고기가 있는 곳으로는 이동 불가, 먹을 수도 없음

 * 탐색의 우선순위
  -- 사방탐색으로 이동 --> 가까운 물고기를 먹어야 하므로 BFS로 탐색해보자.
  -- 가장 가까운 녀석이 1순위
  -- 1순위가 여러 마리일 경우 동일 거리에서 가장 위쪽 물고기
  -- 위쪽 물고기도 여러마리라면 가장 왼쪽 물고기
  -- 탐색 과정에서 우선순위에 기반해서 물고기를 먹기 때문에 PriorityQueue 사용
  -- 동일한 너비의 물고기들을 다 찾은 후 위 우선순위로 물고기 먹기
  -- 가까운데 있는 물고기를 발견하면 다음 너비의 물고기는 찾을 필요 없다.
  -- 물고기를 먹으면 그 지점으로 이동해서 거기를 시작점으로 다음 BFS의 시작

입력사항

 * 공간의 크기 N(2 ≤ N ≤ 20)
 * 공간의 상태는 0, 1, 2, 3, 4, 5, 6, 9
 * 이때 0은 빈칸, 9는 아기 상어, 나머지는 칸에 있는 물고기의 크기
 * 아기상어는 언제나 한마리 존재

출력사항

 * 물고기를 잡아먹을 수 있는 시간 출력

 

동영상 설명

1시간 이상 고민 했지만 아이디어가 떠오르지 않는다면 동영상에서 약간의 힌트를 얻어봅시다.

https://www.youtube.com/watch?v=VPcbnL7JbsI

 

 

소스 보기

동영상 설명을 보고도 전혀 구현이 안된다면 이건 연습 부족입니다.
소스를 보고 작성해 본 후 스스로 백지 상태에서 3번 작성해 볼 의지가 있다면 소스를 살짝 보세요.

package bj.gold.l5;

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

/**
 * @author itsmeyjc
 * @since 2020. 2. 22.
 * @see https://www.acmicpc.net/problem/16236
 * @mem 13748
 * @time 84
 * @caution
 * #bfs - 가장 가까운 물고기를 먹는다.
 * 아기 상어가 물고기에 도달하는 지점까지가 한 번의 BFS. 물고기를 먹으면 그 지점에서 새로운 BFS 시작
 */
public class BJ_G5_16236_아기상어 {
    // 사방탐색용 배열
    static int[][] dir = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

    // 공간의 크기 N(2 ≤ N ≤ 2개시
    static int N;

    static int[][] map;
    static boolean[][] visited;

    // 정답
    static int moveCnt;

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

        N = Integer.parseInt(br.readLine()); // 공간의 크기 N(2 ≤ N ≤ 20)

        map = new int[N][N];

        Shark shark = null;
        StringTokenizer tokens = null;
        for (int r = 0; r < N; r++) {
            tokens = new StringTokenizer(br.readLine());
            for (int c = 0; c < N; c++) {
                map[r][c] = Integer.parseInt(tokens.nextToken());
                // 상어가 있던 지점은 상어를 표시하고 상어는 여기를 다시 지나갈 수 있다.
                if (map[r][c] == 9) {
                    map[r][c] = 0;
                    // 처음 상어의 크기는 2
                    shark = new Shark(r, c, 2, 0, 0);
                }
            }
        }
        /*// 입력값 확인
        for (int[] row : map) {
            System.out.println(Arrays.toString(row));
        }*/

        // 이 상어를 타고 탐색 시작
        bfs(shark);

        System.out.println(moveCnt);

    }

    // 상어가 범위을 확장해가며 물고기를 찾는다.
    static void bfs(Shark shark) {
        Queue<Shark> queue = new LinkedList<>();
        queue.add(shark);
        // 여기가 새로운 상어의 위치 --> 새로 bfs
        visited = new boolean[N][N];
        visited[shark.row][shark.col] = true;

        // 상어와 가장 가까운 물고기의 depth
        int targetDepth = -1;

        // 상어와 가장 가까운 depth에 있는 물고기들
        PriorityQueue<Fish> targetFishList = new PriorityQueue<>();

        Shark front = null;

        // 처음 희생양이 발견된 depth 다음 depth는 돌 필요가 없다.
        findFish: while (!queue.isEmpty()) {
            front = queue.poll();

            for (int d = 0; d < dir.length; d++) {
                int nr = front.row + dir[d][0];
                int nc = front.col + dir[d][1];

                if (isIn(nr, nc) && !visited[nr][nc]) {
                    visited[nr][nc] = true;
                    // 크기가 상어와 같거나 0이면 이동/통과 가능
                    if (map[nr][nc] == 0 || map[nr][nc] == front.size) {
                        queue.add(new Shark(nr, nc, front.size, front.depth + 1, front.eatCnt));
                    }
                    // 먹을 수 있는 녀석이 발견되었다면 해당 물고기를 담아놓자. - 먹이 후보
                    else if (map[nr][nc] < front.size) {
                        // 처음 발견한 물고기여서 targetDepth가 -1이거나 depth가 처음 잡은 놈과 같으면 관심 있다.
                        if (targetDepth == -1 || targetDepth == front.depth + 1) {
                            Fish fish = new Fish(nr, nc, map[nr][nc], front.depth + 1);
                            targetFishList.add(fish);
                            targetDepth = fish.depth;
                        }
                        // depth가 더 큰 녀석이 발견되면 더 이상 돌 필요 없다.
                        else {
                            break findFish;
                        }
                    }
                }
            }
        }

        // 먹을 물고기가 없으면 종료
        if (targetFishList.isEmpty()) {
            return;
        }
        // 물고기가 있으면 먹으러 가자.
        else {
            // PriorityQueue이므로 맨 위의 물고기가 목표
            Fish forEat = targetFishList.poll();

            // System.out.println("먹은놈: " + forEat);
            front.eat(forEat.size);
            // 이제 그 지점에 물고기 없음
            map[forEat.row][forEat.col] = 0;
            // 이동 회수는 업데이트 해주고
            moveCnt += forEat.depth;
            // 이 지점이 새로운 BFS 시점
            bfs(new Shark(forEat.row, forEat.col, front.size, 0, front.eatCnt));
        }
    }


    static boolean isIn(int r, int c) {
        return 0 <= r && 0 <= c && r < N && c < N;
    }

    static class Fish implements Comparable<Fish> {
        int row, col;
        int size; // 크기
        int depth;// 거리

        public Fish(int row, int col, int size, int depth) {
            super();
            this.row = row;
            this.col = col;
            this.size = size;
            this.depth = depth;
        }

        // 1순위 depth, 2순위 세로 위쪽, 3순위 가로 왼쪽
        @Override
        public int compareTo(Fish o) {
            if (depth == o.depth) {
                if (row == o.row) {
                    return Integer.compare(col, o.col);
                } else {
                    return Integer.compare(row, o.row);
                }
            } else {
                return Integer.compare(depth, o.depth);
            }
        }
    }

    static class Shark {
        int row, col;
        int size; // 상어의 크기
        int depth;// 이동 회수
        int eatCnt;// 먹은 회수

        public Shark(int row, int col, int size, int depth, int eatCnt) {
            super();
            this.row = row;
            this.col = col;
            this.size = size;
            this.depth = depth;
            this.eatCnt = eatCnt;
        }

        // 한번에 한 마리씩 먹고 몸집만큼 먹으면 크기 변경
        public void eat(int cnt) {
            // System.out.print("변경 전: 먹은 수: "+eatCnt+", 크기: "+size);
            eatCnt++;
            if (eatCnt == size) {
                // eatCnt-=size;
                eatCnt = 0;
                size++;
            }
        }
    }

    // END:

    static String src = "6\n" +
                        "1 1 1 1 1 1\n" +
                        "2 2 6 2 2 3\n" +
                        "2 2 5 2 2 3\n" +
                        "2 2 2 4 6 3\n" +
                        "0 0 0 0 0 6\n" +
                        "0 0 0 0 0 9";
}