[백준]16236: 아기 상어 - JAVA

[백준]16236: 아기 상어 

www.acmicpc.net/problem/16236

16236번: 아기 상어

풀이

BFS + 구현 문제로 조건이 까다롭고 신경써야 할 조건들이 많아 어렵다고 느껴졌던 문제였다.

 

BFS안에서 현재 이동할 수 있는 곳으로 이동하면서 물고기의 크기가 자신의 크기보다 작으면 먹어주도록 하였다. 물고기의 크기가 자신의 크기보다 작거나 같다면 이동시켜 주었다.

 

자신의 크기보다 작은 물고기를 만나면 모두 ArrayList에 담아준 다음 위쪽 -> 왼쪽 좌표를 비교하며 우선순위에 맞게 먼저 먹을 물고기를 정해주었다.

 

BFS 변형 문제로 나중에 꼭 다시한번 풀어봐야겠다!

 

코드

import java.util.*;
 
public class Main {
    
    static int n;
    static int[][] board;
    static int dx[] = {-1, 0, 1, 0}; //위 왼 아래 오
    static int dy[] = {0, 1, 0, -1};
    static ArrayList<Node> fishes;
    
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        
        n = scan.nextInt(); 
        board = new int[n][n];
        Queue<Node> q = new LinkedList<>();
        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                board[i][j] = scan.nextInt();
                if(board[i][j] == 9){
                    q.add(new Node(i, j, 0));
                    board[i][j] = 0;
                }
            }
        }
        
        int eat = 0;
        int time = 0; 
        int age = 2;
        while(true){
            LinkedList<Node> fish = new LinkedList<>();
            int[][] dist = new int[n][n];
 
            while (!q.isEmpty()) {
                Node current = q.poll();
                
                for(int i=0; i<4; i++){
                    int nx = current.x + dx[i];
                    int ny = current.y + dy[i];
                 
                    if(nx >= 0 && ny >= 0 && nx < n && ny < n && dist[nx][ny]==0 && board[nx][ny] <= age){
                        dist[nx][ny] = dist[current.x][current.y] + 1;
                        q.add(new Node(nx, ny, dist[nx][ny]));
                        if(1 <= board[nx][ny] && board[nx][ny] <= 6 && board[nx][ny] < age) fish.add(new Node(nx, ny, dist[nx][ny]));
                    }
                }
            }
 
            if(fish.size() == 0){
                System.out.println(time);
                return;
            }
 
            Node currentFish = fish.get(0);
            for(int i = 1; i < fish.size(); i++){
                if(currentFish.dist > fish.get(i).dist) {
                    currentFish = fish.get(i);
                }
                else if(currentFish.dist == fish.get(i).dist) {
                    if(currentFish.x > fish.get(i).x) currentFish = fish.get(i);
                    else if(currentFish.x == fish.get(i).x){
                        if(currentFish.y > fish.get(i).y) currentFish = fish.get(i);   
                    }
                }   
            }
             
            time += currentFish.dist;
            eat++;
            board[currentFish.x][currentFish.y] = 0;
            if(eat == age) {
                age++;
                eat = 0;
            }
            q.add(new Node(currentFish.x, currentFish.y, 0));
        }
    }
    
    public static class Node {
        int x;
        int y;
        int dist;
        
        public Node(int x, int y, int dist) {
            super();
            this.x = x;
            this.y = y;
            this.dist = dist;
        }
    }
}