[백준] 16236 - 아기상어 JAVA

Solved.ac Class 완전정복 프로젝트

Class : 3 ~ 3 ++

 

---

링크

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

16236번: 아기 상어

문제

N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1 ×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다.

아기 상어와 물고기는 모두 크기를 가지고 있고, 이 크기는 자연수이다. 가장 처음에 아기 상어의 크기는 2이고, 아기 상어는 1초에 상하좌우로 인접한 한 칸씩 이동한다.

아기 상어는 자신의 크기보다 큰 물고기가 있는 칸은 지나갈 수 없고, 나머지 칸은 모두 지나갈 수 있다. 아기 상어는 자신의 크기보다 작은 물고기만 먹을 수 있다. 따라서, 크기가 같은 물고기는 먹을 수 없지만, 그 물고기가 있는 칸은 지나갈 수 있다.

아기 상어가 어디로 이동할지 결정하는 방법은 아래와 같다.

더 이상 먹을 수 있는 물고기가 공간에 없다면 아기 상어는 엄마 상어에게 도움을 요청한다.
먹을 수 있는 물고기가 1마리라면, 그 물고기를 먹으러 간다.
먹을 수 있는 물고기가 1마리보다 많다면, 거리가 가장 가까운 물고기를 먹으러 간다.
거리는 아기 상어가 있는 칸에서 물고기가 있는 칸으로 이동할 때, 지나야하는 칸의 개수의 최솟값이다.
거리가 가까운 물고기가 많다면, 가장 위에 있는 물고기, 그러한 물고기가 여러 마리라면, 가장 왼쪽에 있는 물고기를 먹는다.
아기 상어의 이동은 1초 걸리고, 물고기를 먹는데 걸리는 시간은 없다고 가정한다. 즉, 아기 상어가 먹을 수 있는 물고기가 있는 칸으로 이동했다면, 이동과 동시에 물고기를 먹는다. 물고기를 먹으면, 그 칸은 빈칸이 된다.

아기 상어는 자신의 크기와 같은 수의 물고기를 먹을 때마다 크기가 1 증가한다. 예를 들어, 크기가 2인 아기 상어는 물고기를 2마리 먹으면 크기가 3이 된다.

공간의 상태가 주어졌을 때, 아기 상어가 몇 초 동안 엄마 상어에게 도움을 요청하지 않고 물고기를 잡아먹을 수 있는지 구하는 프로그램을 작성하시오.

입력
첫째 줄에 공간의 크기 N(2 ≤ N ≤ 20)이 주어진다.

둘째 줄부터 N개의 줄에 공간의 상태가 주어진다. 공간의 상태는 0, 1, 2, 3, 4, 5, 6, 9로 이루어져 있고, 아래와 같은 의미를 가진다.

0: 빈 칸
1, 2, 3, 4, 5, 6: 칸에 있는 물고기의 크기
9: 아기 상어의 위치
아기 상어는 공간에 한 마리 있다.

출력
첫째 줄에 아기 상어가 엄마 상어에게 도움을 요청하지 않고 물고기를 잡아먹을 수 있는 시간을 출력한다.

접근방법

 문제를 제대로 이해하는 것부터가 일이다. 크기가 늘어나는 상어가 먹을 수 있는 물고기를 다 먹고 걸린 시간을 출력하는 문제이다. 문제의 조건을 완벽하게 이해했다면, 사실 어려운 문제라기보다 까다로운 문제였을 수도 있다. 개인적으로 필자는 이해하는데도 오래 걸렸고, 보수에도 상당히 고통스러운 시간을 보내 풀었다. 문제가 조건을 개 얄밉게 명시했기 때문이다. 풀이로 넘어가기 전 다음의 사항들을 정리하고 가자.

 

• 상어는 자기보다 작은 물고기만 먹는다. (몇몇 해설들 보니, 같거나 작은 이라고 잘못 게시되어있는 블로그들이 많던데, 정말 혼란에 빠지기 더 쉽다. 절대 아니다. 오직 지보다 작은놈만 먹는다.)
• 상어의 먹는 기준은 오로지 거리와 방향이다.(물고기 크기는 관계가 없다. 오로지 최단 거리에 있는 물고기 중 상, 좌, 우, 하 기준이다. 명심해야 한다. (필자는 상. 좌. 하. 우로 풀고 고치는데 1시간 넘게 썼다.)
• 레벨 업하면, 먹은 횟수가 초기화된다.(이건 나만 몰랐나...? 먹은 물고기 누적 안된다.)

이 3개를 제대로 모르면, 예제가 이해가 안 되며, 풀기도 전에 '나는 얼마나 멍청한가' 하는 자괴감에 빠지는 스스로를 볼 수 있다.  이 조건을 안다는 가정하에 풀이로 들어가자.

풀이

 해당 문제를 풀기 위해 구현해야 할 것은 크게 3가지이다.

 

1. 최단 거리의 물고기 중 먹을 수 있는 물고기를 구한다. 단 최단거리에 물고기가 여러 개라면, 문제 조건에 입각한 상, 좌, 우, 하의 규칙성으로 우선순위를 판별한다.

 

2. 선택된 물고기를 먹고, 상어를 해당 위치로 옮긴다. 이때, 이전에 있던 상어의 위치, 옮겨진 상어의 위치, 먹은 횟수 및 상어 크기 증가 조건을 수행한다.

 

3. 자기가 먹을 수 있는 물고기가 없을 때까지 1-2번 과정을 반복한다.

 

1번

 상어가 먹을 수만 있다면, 물고기의 크기는 전혀 신경 쓰지 않는다. 최단 거리를 찾기 위해서 너비 중심 탐색인 BFS를 이용해야 한다. BFS는 같은 depths부터 순차 검색하는 특징이 있으므로, 최단거리에 있는 작은 물고기가 먼저 발견된다.

여기서 의문점이 생길 수 있다.

 

아니... depths구별을 어떻게 하냐 그럼? 

 

 depths를 구분하는 방법은 여러 가지가 있으나, 이번 문제에서는 Pair객체에  depth라는 변수를 통해, queue에 들어갈 때 depth값을 함께 넣어 구분했다. 

 

c.f )

 아래의 코드에서 for문을 다 수행하지 않았는데, break를 거는 이유에 대해 의문이 생기신 분들이 충분히 있을 수 있다. 해당 코드는 본 조건이 제시한 상. 좌. 우. 하의 방향성을 그대로 따라가므로, 하나의 노드가 갈 수 있는 4가지 방향 중 먹을 수 있는 물고기가 있다면, 더 이상 탐색의 의미가 없으므로, break를 통해 더 깊은 depths의 유입을 제한한다.

이 경우 주의해야 할 점이 있는데, 같은 depths에 있는 다른 노드들에게도 제한조건을 걸어줘야 한다. (그래야 같은 depths의 다른 노드가 더 이상 밑을 검색하지 않기 때문이다.) 따라서 limit 변수를 만들고, 물고기를 찾은 경우 해당 depths로 limit를 변경하여 흐름 제어를 했다.

 

2번

 사실 1번만 구현했다면, 2번은 크게 어렵지 않다. 여러 개의 물고기가 나왔다면, 상. 좌. 우. 하의 순서로 정렬할 수 있게 정렬 조건을 만들고, 시간 누적, 위치 옮기기, 및 상어 레벨업 확인만 앞서 말했듯이, 상어는 레벨 업하면, 먹은 물고기가 경험치처럼 소모된다.(-_-;) 그러므로 꼭 먹은 횟수를 0으로 바꿔주자. 반대로, 먹을 수 있는 물고기가 아예 없다면, 루프 탈출 조건을 주면 된다.

 

3번 

1번과 2번으로 루프 문을 형성한다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

    public static void main(String[] args) throws IOException {
        Main test = new Main();
    }

    public Main() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

        int[][] arr = new int[N][N];
        Pair shark_loc = null;
        int shark_size = 2;
        for (int i = 0; i < arr.length; i++) {
            String[] rows = br.readLine().split(" ");
            for (int j = 0; j < arr[i].length; j++) {
                if (rows[j].equals("9")) {
                    shark_loc = new Pair(i, j);
                }
                arr[i][j] = Integer.parseInt(rows[j]);
            }
        }

        int result = solution(shark_size, shark_loc, arr);
        System.out.println(result);

    }

    private int solution(int shark_size, Pair shark_loc, int[][] arr) {

        int[][] ways = {{-1, 0}, {0, -1}, {0, 1}, {1, 0}};
        int time = 0;
        int eat_cnt = 0;
        while (true) {


            Queue<Pair> queue = new LinkedList<>();
            queue.add(shark_loc);
            boolean[][] visit = new boolean[arr.length][arr.length];

            //현재 상어위치 저장
            visit[queue.peek().x][queue.peek().y] = true;

          //  System.out.println("현재 상어 위치 : " + shark_loc.x + " , " + shark_loc.y);
            List<Pair> fish_list = new ArrayList<>();
            //먹을 수 있는 물고기가 존재할 때 depths 제한하기 위한 변수
            int limit = 401;

            while (!queue.isEmpty()) {

                Pair cur_loc = queue.poll();

                for (int i = 0; i < ways.length; i++) {
                    Pair next_loc = new Pair(cur_loc.x + ways[i][0], cur_loc.y + ways[i][1]);


                    //물고기를 찾았을 때, 작동 찾은 depths를 초과하면 out 시킴
                    if(limit < cur_loc.depths){
                        break;
                    }
                    //depths control
                    next_loc.depths = cur_loc.depths + 1;
                    //범위 안에 있고
                    if (0 <= next_loc.x && next_loc.x < arr.length && 0 <= next_loc.y && next_loc.y < arr.length) {
                        //방문한적 없으며
                        if (!visit[next_loc.x][next_loc.y]&& arr[next_loc.x][next_loc.y] <= shark_size) {

                            //먹을 수 있는 물고기가 존재한다면 way 순서로 우선순위를 보증하므로 break;
                            //단 그냥 break 걸면 같은 depths의 다른 노드를 제어할 수 없으므로 limit 값 depths로 변경
                            if (arr[next_loc.x][next_loc.y] < shark_size && arr[next_loc.x][next_loc.y] != 0) {
                                fish_list.add(next_loc);
                                visit[next_loc.x][next_loc.y] = true;
                                limit = cur_loc.depths;
                                break;
                            } else  {
                                //이동가능하다면 큐에 넣음
                                queue.add(next_loc);
                                visit[next_loc.x][next_loc.y] = true;

                            }

                        }
                    }
                }

            }

            if (fish_list.isEmpty()) {
             //   System.out.println("해당 경로까지 총 " + time + "이 걸림");
                break;
            }

            if (fish_list.size() > 1) {
                //여러개일땐
                Collections.sort(fish_list, (o1, o2) -> {

                        if (o1.x == o2.x) {
                            return o1.y - o2.y;
                        } else {
                            return o1.x - o2.x;
                        }

                });
            }

            /*
                물고기를 잡았다면
                상어가 있던 위치 0으로 변경
                물고기가 있던 위치 9로 변경
                잡아먹기까지 걸린 시간 누적

             */

            Pair loc = fish_list.get(0);
            //System.out.println("현재 타겟 물고기 위치 : " + loc.x + " , " + loc.y + " 크기 : " + arr[loc.x][loc.y]);
            arr[shark_loc.x][shark_loc.y] = 0;
            arr[loc.x][loc.y] = 9;
            time += loc.depths;
            loc.depths = 0;
            shark_loc = loc;

            //System.out.println("해당 경로까지 총 " + time + "이 걸림");

            /*
                레벨업 조건
                상어 레벨만큼 먹었을 때, lv up
                그리고 eat_cnt는 0으로 초기화화
             */
            eat_cnt++;
            if (shark_size == eat_cnt) {
                shark_size += 1;
                eat_cnt = 0;
            }
//            System.out.println("현재 상어 크기 : " + shark_size + "\t-먹은 물고기 수 : " + eat_cnt);
        }


        return time;
    }

    class Pair {
        int x;
        int y;
        //시간경과용
        int depths = 0;

        public Pair(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }

}

결과

 

 

 하... 본 상어의 크기 증가는 레벨업과 같게 보는 것이 맞는 것 같다. 먹은 게 뱃속에 있어야지 왜 누적을 안 하냐고!! -_-;; 거기에 위와 왼쪽이라는 조건은 주었지만, 그 외엔 조건을 주지 않아 당연히 대칭성 있게 방향을 구현했다가... 엄청나게 시간을 빨렸다.. 그렇다고 블로그에 써놓은 해설 중에 저 사실들을 명시해놓은 블로그들을 못 봐서 오랜만에 혼자 디버깅 돌리면서 솎아냈다.. 다들 빡고순가보다... (그래도 시간은 flex 해서 만족.. :D) 해당 코드에 print 코드는 일부로 지우지 않았다. 혹시 자신의 코드가 안되고 있다면, 이동 경로를 비교해보면, 도움이 될 것 같다.

---

포스팅에 문제가 있거나, 설명이 잘못된 부분 지적 환영합니다.

더 나은 퀄리티의 콘텐츠를 제공할 수 있도록 노력하겠습니다.

읽어주셔서 감사합니다.