bj16236(아기상어)-구현,BFS

푸는 시간은 꽤 걸렸지만, 그리 어렵지는 않은 문제였다.

아기상어 클래스를 만들어줘서 상태를 관리하는 책임을 할당해주었고,

메인에서는 상태 관리 메서드들을 사용해주었다.

 

상어의 다음 먹이를 찾는 메서드에서 분기가 꽤나 복잡했는데, 천천히 풀어보면 되는 문제였다.

구현 문제는 클래스나, 메서드를 되도록 많이 나누고, 각각의 책임 또한 나누어, 메인에서 조합해서 풀면 쉽게 풀릴 것 같다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    static int N, startY, startX;
    static int[][] map;
    static StringTokenizer stringTokenizer;
    static BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
    public static void main(String[] args) throws IOException {
        initialize();
        System.out.println(solve());
    }

    private static int solve() {
        BabyShark babyShark = new BabyShark(startY, startX);
        int time = 0;

        do{
            int[] nextFish = babyShark.getNextFishLoc(map, N);  //다음 먹을 물고기의 위치를 정한다.

            if(nextFish[0] == Integer.MAX_VALUE)break;          //만약, 먹을 물고기가 없을 시

            map[babyShark.y][babyShark.x] = 0;                  //현재 자리 0
            babyShark.gogo(nextFish);                           //다음 물고기로 이동
            time += nextFish[2];                                //시간이 걸림
            map[nextFish[0]][nextFish[1]] = 9;                  //상어가 왔다.

            babyShark.eat();                                    //맛있게 먹자.

            babyShark.sizeUp();                                 //사이즈 업
        }while(true);

        if(time == Integer.MAX_VALUE)return 0;
        return time;
    }

    private static void initialize() throws IOException {
        N = Integer.parseInt(bufferedReader.readLine());
        map = new int[N][N];
        for(int y = 0; y < N; y++){
            stringTokenizer = new StringTokenizer(bufferedReader.readLine());
            for(int x = 0; x < N; x++){
                map[y][x] = Integer.parseInt(stringTokenizer.nextToken());
                if(map[y][x] == 9){
                    startY = y;
                    startX = x;
                }
            }
        }
    }
}

class BabyShark{
    int[] dy = {1,0,-1,0};
    int[] dx = {0,1,0,-1};
    int y;
    int x;
    int current = 0;
    int size = 2;

    public BabyShark(int y, int x) {
        this.y = y;
        this.x = x;
    }

    public void sizeUp(){
        if(size <= current){
            current -= size;
            size++;
        }
    }

    public void eat(){
        current++;
    }

    public int[] getNextFishLoc(int[][] map, int N){
        Queue<int[]> queue = new ArrayDeque<>();
        int[][] minDistance = new int[N][N];
        for(int y = 0; y < N; y++){
            for(int x = 0; x < N; x++){
                minDistance[y][x] = Integer.MAX_VALUE;
            }
        }

        queue.add(new int[]{y,x});
        minDistance[y][x] = 0;

        while(!queue.isEmpty()){
            int[] curr = queue.poll();
            int curr_y = curr[0];
            int curr_x = curr[1];
            for(int i = 0; i < 4; i++){
                int next_y = curr_y + dy[i];
                int next_x = curr_x + dx[i];
                if(next_y >= N || next_y < 0 || next_x >= N || next_x < 0 || map[next_y][next_x] > size)continue;
                if(minDistance[next_y][next_x] <= minDistance[curr_y][curr_x]+1)continue;
                minDistance[next_y][next_x] = minDistance[curr_y][curr_x] + 1;
                queue.add(new int[]{next_y, next_x});
            }
        }

        return getWantFish(map, minDistance, N);
    }

    private int[] getWantFish(int[][] map, int[][] minDistances, int N) {
        int minY = Integer.MAX_VALUE;
        int minX = Integer.MAX_VALUE;
        int minDistance = Integer.MAX_VALUE;
        for(int y = 0; y < N; y++){
            for(int x = 0; x < N; x++){
                if(map[y][x] != 0 && map[y][x] != 9 && minDistance > minDistances[y][x] && size > map[y][x]){
                    minDistance = minDistances[y][x];
                    minY = y;
                    minX = x;
                }else if(map[y][x] != 0 && map[y][x] != 9 && minDistance == minDistances[y][x] && size > map[y][x] && y < minY && minDistance != Integer.MAX_VALUE){
                    minY = y;
                    minX = x;
                }else if(map[y][x] != 0 && map[y][x] != 9 && minDistance == minDistances[y][x] && size > map[y][x] && y == minY && x < minX && minDistance != Integer.MAX_VALUE){
                    minX = x;
                }
            }
        }
        return new int[]{minY, minX, minDistance};
    }

    public void gogo(int[] target){
        this.y = target[0];
        this.x = target[1];
    }
}