[JAVA] 백준 - 아기상어 16236 (BFS)

www.acmicpc.net/problem/16236

16236번: 아기 상어

 

# 풀이

(핵심 로직)

1. BFS 를 사용하여 현재 아기 상어 위치에서 먹을 수 있는 모든 먹이를 찾는다.

2. 가장 가까운 먹이를 찾고 거리가 같다면 왼쪽 위에 있는 먹이를 고른다.

 

 

2번을 구현하기 위해 편하게 Comparable 을 구현하여 Collections 의 정렬 함수를 사용하였지만

메모리도 줄이고 속도도 늘릴 수 있는 방법도 존재한다. 코드가 늘어나고 정렬함수를 사용하더라도 

메모리 사용량이나 속도 면에서 크게 손해는 아니기 때문에 정렬을 선택하였다.

 

 

babySharkWeight 는 현재 아기상어의 무게다.

full 은 한마리 잡아 먹을때 마다 1씩 늘어나며 babySharkWeight와 같아지면 babySharkWeight를 1증가하고

full은 0으로 초기화 해준다.

# 자바 코드

import java.util.LinkedList;
import java.util.*;

class Main{
    static int n;
    static int[][] arr;
    static int babySharkWeight;
    static int full;

    static int[] dx = {-1,1,0,0};
    static int[] dy = {0,0,-1,1};

    static int answer;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        arr = new int[n][n];
        babySharkWeight = 2;

        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                arr[i][j] = sc.nextInt();
            }
        }

        while(true) {
            Pair p = huntingFish();
            if(p.x==-1) break;

            answer+= p.dist;
            full++;
            if(full == babySharkWeight){
                babySharkWeight++;
                full=0;
            }
        }


        System.out.println(answer);

    }

    private static void print2D() {
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                System.out.print(arr[i][j]);
            }
            System.out.println();
        }
    }

    public static Pair huntingFish(){
        ArrayList<Pair> list = new ArrayList<>();
        Queue<Pair> q = new LinkedList<>();
        boolean[][] visited = new boolean[n][n];
        int[] start = new int[2];
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                if(arr[i][j] == 9){
                    visited[i][j] = true;
                    start[0] = i;
                    start[1] = j;
                    q.add(new Pair(i,j,0));
                }
            }
        }
        while(!q.isEmpty()){
            Pair p = q.poll();

            for(int i=0;i<4;i++){
                int nx = p.x + dx[i];
                int ny = p.y + dy[i];
                if(nx<0 || nx>=n || ny<0 || ny>=n) continue;

                if(arr[nx][ny]<=babySharkWeight && visited[nx][ny]==false){
                    visited[nx][ny] = true;
                    if(arr[nx][ny] < babySharkWeight && arr[nx][ny]!=0) {
                        list.add(new Pair(nx,ny,p.dist+1));
                    }
                    else{
                        q.add(new Pair(nx,ny,p.dist+1));
                    }
                }
            }
        }
        if(list.size()==0) return new Pair(-1,-1,-1);
        Collections.sort(list);

        arr[start[0]][start[1]] = 0;
        arr[list.get(0).x][list.get(0).y] = 9;

        return list.get(0);
    }

    static class Pair implements Comparable<Pair>{
        int x,y;
        int dist;

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

        @Override
        public int compareTo(Pair other){
            if(this.dist != other.dist) return this.dist - other.dist;
            if(this.x != other.x ) return this.x - other.x;
            return this.y - other.y;
        }

        @Override
        public String toString() {
            return "Pair{" +
                    "x=" + x +
                    ", y=" + y +
                    ", dist=" + dist +
                    '}';
        }
    }
}