백준 - 아기상어(JAVA)

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

16236번: 아기 상어

 

문제설명

BFS 와 객체 비교, PQ와 queue를 사용한다. 복잡한 문제여서 잘 읽어보며 꼼꼼히 코딩해야한다.

 

알고리즘

1. 우선순위를 compareTo를 이용하여 설정한다. 현재 위치를 queue에 넣고 BFS 실행

2. 먹이를 먹으면 PQ에 넣는다. 이떄 먹이를 먹을 때 까지의 최소시간 min을 이용해서 최소시간에 먹이를 먹은 애들만 PQ에 넣는다. -> queue 비워짐

3. PQ에서 조건에 맞게 정렬됨으로 가장 peek을 이용하여 가장 위에 있는 먹이 좌표를 queue에 넣는다. 그리고 PQ를 초기화한다.

4. 2,3을 반복한다.

 

주의사항

1. queue와 pq를 의 종료 조건 설정 조건을 잘 설정해야한다.

 

구현

class fish implements Comparable<fish>{
    int y;
    int x;
    int dis;
    public fish(int y, int x, int dis) {
        super();
        this.y = y;
        this.x = x;
        this.dis = dis;
    }
    @Override
    public int compareTo(fish o) {
        if(this.dis > o.dis)
            return 1;
        else if(this.dis < o.dis)
            return -1;
        else
        {
            if(this.y > o.y)
                return 1;
            else if(this.y < o.y)
                return -1;
            else
            {
                if(this.x > o.x)
                    return 1;
                else if(this.x < o.x)
                    return -1;
            }
        }
        return 0;
    }

}
class Main
{
    static int map[][];
    static int N;
    static int dir[][] = {{-1,0},{1,0},{0,-1},{0,1}};
    static boolean check[][];
    public static void main(String args[]) throws Exception
    {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        //StringTokenizer s = new StringTokenizer(in.readLine()," ");
        N = Integer.parseInt(in.readLine().trim());
        map = new int[N][N];
        PriorityQueue<fish> pq = new PriorityQueue<fish>();
        LinkedList<int []> queue = new LinkedList<int[]>();

        for (int i = 0; i < N; i++) {
            StringTokenizer s = new StringTokenizer(in.readLine()," ");
            for (int j = 0; j < N; j++) {
                map[i][j] = Integer.parseInt(s.nextToken());
                if(map[i][j] == 9)
                {
                    map[i][j] = 0;
                    queue.offer(new int[] {i,j,2,0});
                }
            }
        }
        fish f;
        int result=0;
        int cnt=0;
        int loc_size=2;
        while(true)
        {
            check = new boolean[N][N];
            int min = 1600;
            //먹이 찾는 과정
            while(!queue.isEmpty()) //bfs
            {
                int [] temp = queue.poll();
                int y = temp[0];
                int x = temp[1];
                int size = temp[2];
                int time = temp[3];
                if(time > min)
                {
                    queue.clear();
                    break;
                }
                //System.out.println("y= "+y+" x= "+x+" size= "+size+" time= "+time);
                for (int i1 = 0; i1 < 4; i1++) {
                    int ny = dir[i1][0]+y;
                    int nx = dir[i1][1]+x;
                    if(ny > -1 && ny < N && nx < N && nx>-1 && !check[ny][nx])
                    {
                        if(map[ny][nx] == 0 || map[ny][nx] == size)    //길찾기용
                        {
                            check[ny][nx] = true;
                            queue.offer(new int[] {ny,nx,size,time+1});
                        }
                        else if(map[ny][nx] != 0 &&map[ny][nx] < size) //먹이찾기용
                        {
                            check[ny][nx] = true;
                            //System.out.println("ny= "+ny+" nx= "+nx+" time= "+time);
                            pq.offer(new fish(ny, nx, time+1)); //원래 pq면 알아서 되는데 시간 줄이기위한 방법
                            if(min > time)
                                min = time;
                        }
                    }
                }//end for
            }//end while
            if(pq.isEmpty()) //먹이 못찾으면
                break;
            f = pq.peek();

            result+=f.dis;
            map[f.y][f.x] = 0;
            cnt++;
            if(cnt == loc_size)
            {
                loc_size++;
                cnt=0;
            }
            queue.offer(new int[] {f.y,f.x,loc_size,0}); //상어위치 재초기화
            pq.clear(); //초기화

        }
        System.out.println(result);
    }        
}