16236. 아기 상어

문제 개요

아기 상어가 더 이상 먹을 수 있는 물고기가 없을 때까지 걸리는 시간을 구하는 문제입니다.

문제 접근

상어가 이동할 다음 위치를 찾는 방법은 BFS를 이용하면 됩니다. 다만, 주의해야 할 점이 같은 거리에 있더라도 위쪽 우선, 왼쪽 우선이기 때문에 먹을 수 있는 최소 거리의 물고기를 발견했어도 다른 위치를 좀 더 탐색해 보아야 합니다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Objects;
import java.util.Queue;

class Pos{
    private int row;
    private int col;
    static final int[][] dirs = {
        {-1, 0},
        {0, -1},
        {0, 1},
        {1, 0}
    };

    public Pos(int row, int col){
        this.row = row;
        this.col = col;
    }

    public int getRow() {
        return row;
    }
    public void setRow(int row) {
        this.row = row;
    }
    public int getCol() {
        return col;
    }
    public void setCol(int col) {
        this.col = col;
    }

    public boolean isIn(int N){
        return row >=0 && row < N && col >= 0 && col < N;
    }

    public Pos move(int dir){
        return new Pos(row + dirs[dir][0], col + dirs[dir][1]);
    }

    @Override
    public boolean equals(Object obj) {
        if(obj == this){
            return true;
        }
        if(obj == null || obj.getClass() != this.getClass()){
            return false;
        }
        Pos other = (Pos)obj;
        return row == other.row && col == other.col;
    }

    @Override
    public int hashCode() {
        return Objects.hash(row, col);
    }
}

class Shark{
    private static final int defaultSize = 2;
    private Pos pos;
    private int size;
    private int eat;

    public Shark(Pos pos){
        this.pos = pos;
        this.size = defaultSize;
        this.eat = 0;
    }

    public static int getDefaultsize() {
        return defaultSize;
    }

    public Pos getPos() {
        return pos;
    }

    public void setPos(Pos pos) {
        this.pos = pos;
    }

    public int getSize() {
        return size;
    }

    public void setSize(int size) {
        this.size = size;
    }

    public boolean isEatable(int size){
        return this.size > size;
    }

    public void eatFish(){
        this.eat++;
        if(eat == size){
            size++;
            eat = 0;
        }
    }
}

public class Main {
    static int N;
    static int[][] spaces;
    static String testName;

    static void input() throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(bf.readLine());
        spaces = new int[N][];
        for(int i=0;i<N;i++){
            spaces[i] = Arrays.stream(bf.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        }
    }

    static Pos findFish(Shark shark){
        Queue<Pos> queue = new LinkedList<>();
        Queue<Integer> distances = new LinkedList<>();
        boolean[][] isVisited = new boolean[N][N];
        queue.add(shark.getPos());
        isVisited[shark.getPos().getRow()][shark.getPos().getCol()] = true;
        distances.add(0);

        Pos tempPos = null;
        int tempDis = 0;

        while(!queue.isEmpty()){
            Pos cur = queue.remove();
            int distance = distances.remove();
            for(int d=0; d<4; d++){
                Pos next = cur.move(d);
                if(!next.isIn(N)){
                    continue;
                }
                if(isVisited[next.getRow()][next.getCol()]){
                    continue;
                }
                if(spaces[next.getRow()][next.getCol()] == 0 || spaces[next.getRow()][next.getCol()] == shark.getSize()){
                    queue.add(next);
                    isVisited[next.getRow()][next.getCol()] = true;
                    distances.add(distance+1);
                    continue;
                }
                if(!shark.isEatable(spaces[next.getRow()][next.getCol()])){
                    continue;
                }
                if(tempPos == null){
                    tempPos = next;
                    tempDis = distance + 1;
                    continue;
                }
                if(distance + 1 > tempDis){
                    spaces[tempPos.getRow()][tempPos.getCol()] = tempDis;
                    return tempPos;
                }
                if(tempPos.getRow() == next.getRow() && tempPos.getCol() > next.getCol()){
                    tempPos = next;
                    continue;
                }
                if(tempPos.getRow() > next.getRow()){
                    tempPos = next;
                    continue;
                }   
            }
        }
        if(tempPos == null){
            return shark.getPos();
        }
        spaces[tempPos.getRow()][tempPos.getCol()] = tempDis;
        return tempPos;
    }

    static void process() throws IOException {
        Shark shark = new Shark(new Pos(0, 0));

        for(int i=0;i<N;i++){
            for(int j=0;j<N;j++){
                if(spaces[i][j] != 9){
                    continue;
                }
                shark.setPos(new Pos(i, j));
                spaces[i][j] = 0;
            }
        }

        int time = 0;


        Pos cur = findFish(shark);
        while(cur != shark.getPos()){
            time += spaces[cur.getRow()][cur.getCol()];
            shark.setPos(cur);
            shark.eatFish();
            spaces[cur.getRow()][cur.getCol()] = 0;
            cur = findFish(shark);
        }


        System.out.println(time);
    }

    public static void main(String[] args) throws IOException{
        input();
        process();
    }
}

문제

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