[백준] 아기 상어 - 16236번

문제설명

www.acmicpc.net/problem/16236

16236번: 아기 상어

기본아이디어

아기 상어가 먹이를 찾아다니는 문제입니다. 저는 단계별로 생각하고 하나씩 구현을 했습니다.

1. 아기 상어 위치에서 가장 가까운 먹이들을 찾습니다.

2. 같은 거리에 있는 먹이들을 발견하면 먹이들을 모았다가 조건에 맞는 가장 위에 그리고 가장 왼쪽에 있는 먹이를 선택해서 아기 상어 위치를 이동시킵니다.

3. 그리고 다시 위에 했던 작업들을 반복합니다.

 

처음에는 가장 위, 가장 좌측에 있는 먹이를 찾는 작업을 BFS탐색에서 탐색순서를 위, 좌, 우, 아래로 하면 자동으로 가장 위쪽, 좌측에 있는 먹이를 먼저 선택할 거라 생각을 했는데, 그렇지 않았습니다.

가장 간단한 반례를 들자면 두 먹이의 위치가 현재 위치에서 좌1아래1, 우1우1 이렇게 있다고 가정을 하면 좌1아래1이 먼저 큐에서 나오게 되서 먹이 탐색의 조건을 만족하지 못하게 됩니다. 그래서 결국 같은 위치에 있는 먹이들을 다 PriortyQueue에 넣고 조건을 검사하도록 했습니다.

 

구현코드

public static void main(String[] args) throws IOException {
        N = Integer.parseInt(input.readLine());
        map = new int[N][];
        StringTokenizer st;
        for(int i = 0; i < N; i++){
            st = new StringTokenizer(input.readLine());
            int[] temp = new int[N];
            for(int j = 0; j < N; j++)
                temp[j] = Integer.parseInt(st.nextToken());
            map[i] = temp;
        }
        System.out.println(bfs());
    }
    static int N;
    static int[][] map;
    static int[] dr = {-1, 0, 0, 1}; // 상 좌 하 우
    static int[] dc = {0, -1, 1, 0};
 
    static int bfs(){
        int result = 0;
        Queue<int[]> queue = new LinkedList<>();
        boolean[][] visited = new boolean[N][N];
        out:for(int i = 0; i < N; i++){
            for(int j = 0; j < N; j++){
                if(map[i][j] == 9){
                    queue.add(new int[]{i, j});
                    map[i][j] = 0;
                    visited[i][j] = true;
                    break out;
                }
            }
        }
        int size = 2;
        int eat = 0;
        int movemet = 0;
        boolean found = false;
        PriorityQueue<int[]> pq = new PriorityQueue<>(new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                if(o1[0] == o2[0])
                    return  o1[1] - o2[1];
                return o1[0] - o2[0];
            }
        });
 
        while(!queue.isEmpty()){
            int q_size = queue.size();
            movemet++;
            out:for(int i = 0; i < q_size; i++){
                int[] loc = queue.poll();
                for(int d = 0; d < 4; d++){
                    int nr = loc[0] + dr[d];
                    int nc = loc[1] + dc[d];
                    if(isIn(nr,nc) && !visited[nr][nc] && map[nr][nc] <= size){
                        if(map[nr][nc] >= 1 && map[nr][nc] < size){
                            pq.add(new int[]{nr,nc});
                            found = true;
 
                        }else{
                            queue.add(new int[]{nr, nc});
                            visited[nr][nc] = true;
                        }
                    }
                }
            }
            if(found){
                if(size == ++eat){
                    size++;
                    eat = 0;
                }
                int[] select = pq.poll();
                int nr = select[0];
                int nc = select[1];
                queue.clear();
                pq.clear();
                visited = new boolean[N][N];
                map[nr][nc] = 0;
                queue.add(new int[]{nr, nc});
                visited[nr][nc] = true;
                result += movemet;
                movemet = 0;
                found = false;
            }
        }
 
        return result;
    }
    static boolean isIn(int r, int c){
        return r >= 0 && r < N && c >= 0 && c < N;
    }
 
 
 
 
 
 

 

 

정리, 기억할 내용

1. 이번처럼 같은 거리에서 가장 위, 가장 좌측  이러한 조건이 나왔을 때 간단하게 해도 되는지 생각하자.

2. 구현해야할 것들을 단계별로 정리하고 구현을 시작하자.

3. 되도록 함수로 나눠서 구현하자. -> 문제 생기는 곳 찾기 쉽게, 고치기 쉽게