[BOJ] 아기 상어 - 16236(Java)

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

16236번: 아기 상어

[풀이]

 

조건 1. 아기 상어는 자신보다 큰 물고기가 있는 칸은 지나갈 수 없다.

조건 2. 아기 상어는 빈칸(0) 또는 자신과 크기가 같은 물고기 칸은 지나갈 수 있다.

조건 3. 먹을 수 있는 물고기가 없다면 프로그램종료, 1마리가 있다면 바로 그 물고기를 먹으러 가고 여러마리라면

    맨 위쪽 물고기부터, 그 경우도 여러가지라면 맨 왼쪽 물고기부터 먹을 수 있다.

 

3번 조건을 해결하기 위해 Comparable interface의 compareTo 함수를 이용했다.

 

로직 순서는

 

• 입력받은 값 중 9인 칸에 아기상어를 위치시킨다.
• 아기 상어의 위치에서부터 BFS를  실행하면서 위의 조건들을 만족하는 물고기들을 미리 List에 담아둔다.(정렬하기 위해서)
• 그 물고기들 중에서 가장 가까운 거리(min)인 녀석을 먹고 상어를 이동시켜준다.

[소스코드]

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

public class BOJ_16236 {
    static int n, time, min, cnt, sx, sy;
    static int[][] map;
    static boolean[][] visited;
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};
    //가장 왼쪽 -> x, y값이 제일 작은 순서대로
    static public class Fish implements Comparable<Fish>{
        int x;
        int y;
        int val;
        int dist;
        Fish(int x, int y, int val, int dist){
            this.x = x;
            this.y = y;
            this.val = val;
            this.dist = dist;
        }

        @Override
        public int compareTo(Fish o) {
            if(this.x == o.x)
                return Integer.compare(this.y, o.y);
            else
                return Integer.compare(this.x, o.x);
        }
    }
    //상어가 주어진 조건들을 만족하는 물고기들을 관리할 List
    static List<Fish> eatableList;
    
    //상어가 물고기들을 찾기 위해 BFS를 사용해야함(최소 칸 수를 구하기 위해)
    static Queue<Fish> q;
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        n = Integer.parseInt(st.nextToken());

        map = new int[n][n];

        q = new LinkedList<>();

        for(int i=0;i<n;i++){
            st = new StringTokenizer(br.readLine());
            for(int j=0;j<n;j++){
                map[i][j] = Integer.parseInt(st.nextToken());
                //입력과 동시에 아기 상어를 Queue에 넣어준다.
                if(map[i][j] == 9){
                    q.offer(new Fish(i, j, 2, 0));
                    sx = i;
                    sy = j;
                }
            }
        }

        map[sx][sy] = 0;
        cnt = 0;
        time = 0;
        while(true){
            eatableList = new ArrayList<>();
            Fish curShark = q.peek();
            visited = new boolean[n][n];
            min = Integer.MAX_VALUE;

            int sharkSize = curShark.val;       //현재 상어의 크기와 물고기를 먹은 횟수
			
            //아기 상어의 크기와 먹은 물고기의 마릿수가 같으면 몸무게를 증가시키는데
            //물고기를 먹는경우에 처리를 안해줘서 .. 위에 빼놨음
            if(sharkSize == cnt){
                sharkSize++;
                q.poll();
                q.offer(new Fish(curShark.x, curShark.y, sharkSize, curShark.dist));
                cnt = 0;
            }
            while(!q.isEmpty()){
                Fish shark = q.poll();
                int cx = shark.x;
                int cy = shark.y;
                int cv = shark.val;
                int cd = shark.dist;
                for(int i=0;i<4;i++){
                    int nx = cx+dx[i];
                    int ny = cy+dy[i];
                    if(nx < 0 || ny < 0 || nx >= n || ny >= n) continue;
                    if(!visited[nx][ny]){
                        if(map[nx][ny] == 0 || map[nx][ny] == cv){       //방문하지 않은 빈칸 or 상어의 크기와 같은 칸이면 방문체크 & 현재거리(cd)를 +1
                            q.offer(new Fish(nx, ny, cv, cd+1));
                        }
                        else if(map[nx][ny] > 0 && map[nx][ny] <= 6 && map[nx][ny] < cv){  //먹을 수 있는 물고기라면 일단 리스트에 담아둔다
                            eatableList.add(new Fish(nx, ny, map[nx][ny], cd+1));
                            min = Math.min(min, cd+1);                               //그 중에서 최소거리를 저장해놓음
                        }															//compareTo 함수에 최소거리인 경우는 정의안해놔서 여기로빼놨음
                        visited[nx][ny] = true;
                    }
                }
            }
            //상어의 위치에서부터 물고기들을 찾았는데 사이즈가 0이라면 엄마찾아가야함
            if(eatableList.size() == 0){
                System.out.println(time);
                System.exit(0);
            }
            //그게 아니라면 상어로 부터 가장 가까운 물고기를 찾는다.
            //만약 가까운 물고기가 여러마리라면 맨 위부터, 그 물고기도 많다면 맨 왼쪽부터

            Collections.sort(eatableList);
            for(int i=0;i<eatableList.size();i++){
                Fish cur = eatableList.get(i);
                int curDist = cur.dist;
                if(curDist == min){
                    map[cur.x][cur.y] = 0;
                    cnt++;
                    time += curDist;
                    q.offer(new Fish(cur.x, cur.y, sharkSize, 0));
                    break;
                }
            }
        }
    }
}