[JAVA] 백준 16236 - 아기 상어

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

2차원 배열에서 주어지는 아기상어의 위치에서 이동하며 주어진 규칙에 따라 물고기를 먹을 수 있을 만큼 먹었을 때 이동거리를 구하는 문제이다. 

내가 생각한 로직은 BFS를 이용해서 아기상어 위치를 기준으로 먹을 수 있는 가장 좌측 상단의 물고기까지의 이동 거리를 구하고, 먹은 물고기의 위치를 기준으로 다시 BFS를 돌리는 과정을 반복해 이동이 불가능할때까지의 depth를 구하는 것이었다. 

구현을 완료하고 예제를 돌려보니 틀린 점이 있어서 보니까 가장 좌측 상단의 물고기를 구하지 않고 먹을 수 있는 물고기를 찾으면 break하도록 구현해놨던 것이다. 

그래서 각 DFS마다 최단거리로 이동한 먹을 수 있는 물고기 위치의 최소행, 행이 같을 경우 최소 열값을 저장해 해당 값으로 이동하는 조건을 추가해 통과했다.

조건절을 처음에 더 심도 있게 봤었으면 더 빠르게 풀지 않았을까 싶다.

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

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

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int size = par(br.readLine());
        int[][] map = new int[size][size];
        Pos start = new Pos();
        int curSize = 2;
        int eat = 0;
        int totalDepth = 0;
        for (int i = 0; i < size; i++) {
            map[i] = getArray(br.readLine());
            for (int j = 0; j < size; j++) {
                if (map[i][j] == 9) {
                    start = new Pos(i, j, 0);
                    map[i][j] = 0;
                }
            }
        }
        Queue<Pos> q = new LinkedList<>();
        while (mapCheck(map, curSize)) {
            int mini = 21;
            int minj = 21;
            int minDepth = 9999999;
            q.clear();
            q.offer(start);
            boolean[][] visited = new boolean[size][size];
            while (!q.isEmpty()) {
                Pos p = q.poll();
                int i = p.i;
                int j = p.j;
                int depth = p.depth;
                int value = map[i][j];

                if (value < curSize && value != 0) {
                    minDepth = Math.min(minDepth,depth);
                    if(mini>i && depth==minDepth){
                        mini = i;
                        minj = j;
                    }
                    else if(mini==i&&depth==minDepth){
                        if(minj>j){
                            minj = j;
                        }
                    }
                    continue;
                }
                for (int k = 0; k < 4; k++) {
                    if (check(map, i + dx[k], j + dy[k], visited, curSize)) {
                        q.offer(new Pos(i + dx[k], j + dy[k], depth + 1));
                        visited[i+dx[k]][j+dy[k]] = true;
                    }
                }
            }
            eat++;
            if (eat == curSize) {
                eat = 0;
                curSize++;
            }if(mini==21) break;
            start = new Pos(mini, minj, minDepth);
            map[mini][minj] = 0;
            totalDepth = minDepth;
        }
        System.out.println(totalDepth);
    }

    static boolean check(int[][] map, int i, int j, boolean[][] visited, int curSize) {
        if (i < 0 || i >= map.length || j < 0 || j >= map.length) return false;
        if (visited[i][j]) return false;
        if (map[i][j] > curSize) return false;
        return true;
    }

    static boolean mapCheck(int[][] map, int curSize) {
        for (int i = 0; i < map.length; i++) {
            for (int j = 0; j < map.length; j++) {
                if (map[i][j] != 0 && map[i][j] != 9&&curSize>map[i][j]) {
                    return true;
                }
            }
        }
        return false;
    }

    static int par(String s) {
        return Integer.parseInt(s);
    }

    static int[] getArray(String s) {
        return Arrays.stream(s.split(" ")).mapToInt(Integer::parseInt).toArray();
    }
}

class Pos {
    int i;
    int j;
    int depth;

    Pos() {
    }

    Pos(int i, int j, int depth) {
        this.i = i;
        this.j = j;
        this.depth = depth;
    }
}