[Java] 백준 16236. 아기 상어

문제

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

16236번: 아기 상어

 

알아야 할 개념

• 2차원 배열 BFS 탐색

풀이

주어진 조건에 따라 bfs 시뮬레이션을 구현하는 문제.

풀이 알고리즘은 다음과 같다.

1. 현재 위치에서 bfs 탐색을 하며 currentSIze 보다 작은 상어들을 priorityQueue에 추가한다.
2. priorityQueue 가 비어 있지 않은 경우 하나 꺼내서 잡아먹는다.
   1. 시간, 상어 사이즈 갱신한다.
   2. 지금까지의 PriorytyQueue와 Queue, bool visit array 를 리셋한다.
3. 정답을 리턴한다.

 

이번 bfs 문제의 POV는 

PriorityQueue<int[]> PQ = new PriorityQueue<>((a, b) -> a[0] - b[0] == 0 ? a[1] - b[1] : a[0] - b[0]);

 

pq에 먹을 수 있는 상어의 위치들을  O(log n ) 연산으로 추가한 다음,O(1) 연산으로 하나 꺼내어 시뮬레이션 할떄 시간을 단축한다. (anonymous함수 를 사용한 PQ 생성자가 익숙하지 않으면 연습이 필요하다. )

 

처음에 큐에 추가할때 map 업데이트를 안해서 틀렸다.

백준 구현 문제들은 알고리즘은 어렵지 않으나  어느 부분에서 틀렸는지 디버깅에서 시간이 많이 걸린다.

코드

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

public class Main {
    int dx[] = {0, 0, 1, -1};
    int dy[] = {1, -1, 0, 0};
    public static void main(String args[]) throws IOException {
        Main m = new Main();
        m.solution();
    }
    public void solution() throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st ;
        int N = Integer.parseInt(br.readLine());
        int map [][] = new int[N][N];
        int fishCnt = 0;
        boolean needHelp = false;
        Queue<int[]> Q = new LinkedList<>();
        PriorityQueue<int[]> PQ = new PriorityQueue<>((a, b) -> a[0] - b[0] == 0 ? a[1] - b[1] : a[0] - b[0]);
        int sharkSize = 2;//아기상어 사이즈
        int L = 0;
        int c[];
        int x=0, y=0;
        int nx, ny;
        int exp = sharkSize;
        int size ;
        int time= 0;
        boolean v[][] = new boolean[N][N];
        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());
                if(map[i][j] == 9){
                    x = i;
                    y = j;
                }else if(map[i][j] >0)fishCnt++;
            }
        }
        v[x][y] = true;
        Q.offer(new int[]{x,y});
        map[x][y] = 0;

        while(fishCnt > 0 && !needHelp){
            size = Q.size();

            for(int i = 0 ;i < size;i ++){
                c = Q.poll();
                x = c[0];
                y = c[1];
                //System.out.println("현재 위치"+Arrays.toString(c));
                for(int k = 0 ;k <4 ;k++){
                    nx = x +dx[k];
                    ny = y + dy[k];
                    if(nx < 0 || ny < 0 || nx > N-1 || ny > N-1 ||  map[nx][ny] > sharkSize || v[nx][ny])continue;
                    if(map [nx][ny] > 0 && map[nx][ny] < sharkSize){
                        PQ.offer(new int[]{nx,ny});
                    }
                    Q.offer(new int[]{nx, ny});
                    v[nx][ny] = true;
                }
            }
            L++;
            if(!PQ.isEmpty()){
                c = PQ.poll();
                exp--;
                if(exp == 0 ){//level up
                    sharkSize ++;
                    exp = sharkSize;
                }

                //System.out.println("잡음 : " + Arrays.toString(c) + "사이즈 :"+sharkSize);

                Q.removeAll(Q);
                PQ.removeAll(PQ);
                Q.offer(c);
                time += L;
                map[c[0]][c[1]] = 0;
                fishCnt--;
                L=0;
                v = new boolean[N][N];
            }
            if(fishCnt == 0 || Q.isEmpty()){
                needHelp = true;
            }
        }
        System.out.println(time);

    }
}