[백준] 16236 아기 상어 (Java)

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

16236번: 아기 상어

 

bfs 문제이지만, 몇가지 신경써야 할 점이 있다.

1. 타겟(가까운 물고기)이 복수라면, x좌표가 작은 물고기, 그것 또한 복수라면 y좌표가 작은 물고기를 찾아 이동

2. 아기 상어의 상태인 x, y, size, eat 의 관리

3. eat가 size와 같아 졌을 때 size 증가, eat 초기화

4. 잡아먹은 물고기 좌표값 초기화

5. 아기 상어가 목표를 잃을 때 까지 반복

 

해결

1. Queue대신 PriorityQueue를 사용하고, 람다를 이용해 정렬기준 변경

2. x, y, 이동 횟수를 클래스에 저장하여 사용하거나, pq에 int[]{x, y, move} 형태로 바로 저장. eat, size 는 변수로 관리

3. 현재 위치인 cur을 검증하여 사냥 가능한 물고기라면 사냥하고 bfs를 break하여 바깥 while문으로 돌아감

    바깥 while문에서 size == eat 일 시, size 증가, eat 초기화

4. 3번에서 함께 해결

5. 바깥 while문에서 flag변수를 false로 선언, 안쪽 while문(bfs)에서 사냥을 하지 못하고 빠져나왔다면 바깥 while문 break

 

import java.io.*;
import java.util.*;

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

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int n = Integer.parseInt(br.readLine());
        board = new int[n][n];
        int[] cur = null;


        for(int i = 0; i < n; i++){
            st = new StringTokenizer(br.readLine());
            for(int j = 0; j < n; j++){
                board[i][j] = Integer.parseInt(st.nextToken());

                if(board[i][j] == 9){
                    cur = new int[]{i, j};
                    board[i][j] = 0;
                }
            }
        }

        int size = 2;
        int eat = 0;
        int move = 0;

        while(true){
            PriorityQueue<int[]> q = new PriorityQueue<>((o1, o2) ->
                    o1[2] != o2[2] ? Integer.compare(o1[2], o2[2]) : (o1[0] != o2[0] ? Integer.compare(o1[0], o2[0]) : Integer.compare(o1[1], o2[1]))
            );
            boolean[][] visit = new boolean[n][n];

            q.add(new int[]{cur[0], cur[1], 0});
            visit[cur[0]][cur[1]] = true;

            boolean ck = false;

            while(!q.isEmpty()){
                cur = q.poll();

                if(board[cur[0]][cur[1]] != 0 && board[cur[0]][cur[1]] < size){
                    board[cur[0]][cur[1]] = 0;
                    eat++;
                    move += cur[2];
                    ck = true;
                    break;
                }

                for(int i = 0; i < 4; i++){
                    int nx = dx[i] + cur[0];
                    int ny = dy[i] + cur[1];

                    if(nx < 0 || ny < 0 || nx >= n || ny >= n || visit[nx][ny] || board[nx][ny] > size)
                        continue;

                    q.add(new int[]{nx, ny, cur[2] + 1});
                    visit[nx][ny] = true;
                }
            }

            if(!ck)
                break;

            if(size == eat){
                size++;
                eat = 0;
            }
        }
        System.out.println(move);
    }
}

 

코드만 보면 간단한 문제였지만, 신경쓸게 많아서 많이 헤맸다.

또, 여러 과제를 해결하는 도중이라 변수보다 클래스 변수를 선호하게 되는 경향이 생겨버렸다.

알고리즘을 풀면서는 굉장한 악영향을 끼칠 것 같아 조심해야 겠다.