BOJ(백준 온라인 저지) 16236번 with 자바[JAVA]

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

---

BFS 를 통해 최단거리를 구하는 문제인 것 같다.

다만 같은 거리일 경우의 우선순위(* row index 가 작은게 먼저, col index 가 작은게 먼저) 가 추가적으로 붙어있다.

그 외의 것들은 크게 다르지 않다.

 

이런식으로 쭉 풀어봤는데... 메모리 초과가 떴다. 처음이었다.

 

Point 클래스를 너무 남발하면 그럴 수 있다더라...

앞으로는 메모리도 좀 신경쓰면서 구현해야겠다.

 

처음에는 모든 가능한 노드에 대해 Point 객체를 생성해서 비교했었다. 이런 불필요한 인스턴스들은 메모리를 많이 잡아먹을 수 있다. 그래서 이동 가능할 수 있는 노드들을 Point 객체가 아닌, 그냥 row index 와 col index 를 이용했다.

 

또한 그 전에는 Point 객체에 dist(* 거리) 도 멤버변수로 넣어주었다. 이렇게 가능한 Point 객체에 대해 dist 멤버변수를 위한 메모리 공간까지 할당해줘야 하니 메모리 부족이 떴었다.

그래서 dist 2-d array 를 만들어서 BFS 를 수행할 때 마다 초기화 하는 방식으로 dist 멤버 변수를 Point 객체에서 빼주었다.

(* Visited 도 마찬가지)

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    public static List<Point> eatablePoints = new ArrayList<>();
    public static boolean[][] visited;
    public static int[][] distance;
    public static int N;
    public static int[][] space;
    public static int sharkSize = 2;
    public static int time = 0;
    public static int[] dr = {0, 0, 1, -1};
    public static int[] dc = {1, -1, 0, 0};
    public static Point sharkPoint = new Point();
    public static int growUpStack = 0;

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        // N은 공간의 크기
        N = Integer.parseInt(br.readLine());

        // space는 2차원 배열
        space = new int[N][N];
        for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++) {
                int x = Integer.parseInt(st.nextToken());
                space[i][j] = x;
                if (x == 9) {
                    sharkPoint.row = i;
                    sharkPoint.col = j;
                }
            }
        }
        visited = new boolean[N][N];
        distance = new int[N][N];
        
        while (true) {
            for (int i = 0; i < N; i++) {
                Arrays.fill(visited[i], false);
                Arrays.fill(distance[i], 0);
            }
            eatablePoints.clear();
            if (!BFS())
                break;
        }

        System.out.println(time);
    }

    private static boolean BFS() {
        Queue<Point> queue = new LinkedList<>();
        queue.add(new Point(sharkPoint.row, sharkPoint.col));
        visited[sharkPoint.row][sharkPoint.col] = true;
        distance[sharkPoint.row][sharkPoint.col] = 0;

        while (!queue.isEmpty()) {
            Point curPoint = queue.poll();

            for (int i = 0; i < 4; i++) {
                int newRow = curPoint.row + dr[i];
                int newCol = curPoint.col + dc[i];

                if (newRow < 0 || newRow >= N || newCol < 0 || newCol >= N)
                    continue;

                if (visited[newRow][newCol])
                    continue;

                if (space[newRow][newCol] > sharkSize)
                    continue;

                visited[newRow][newCol] = true;
                distance[newRow][newCol] = distance[curPoint.row][curPoint.col] + 1;
                queue.add(new Point(newRow, newCol));

                if (space[newRow][newCol] < sharkSize && space[newRow][newCol] != 0) {
                    eatablePoints.add(new Point(newRow, newCol));
                }
            }
        }

        if (!eatablePoints.isEmpty()) {
            Point targetPoint = Collections.min(eatablePoints, Comparator
                    .comparingInt((Point p) -> distance[p.row][p.col])
                    .thenComparingInt(p -> p.row)
                    .thenComparingInt(p -> p.col));

            space[targetPoint.row][targetPoint.col] = 9;
            space[sharkPoint.row][sharkPoint.col] = 0;

            sharkPoint.row = targetPoint.row;
            sharkPoint.col = targetPoint.col;

            growUpStack++;
            if (growUpStack == sharkSize) {
                sharkSize++;
                growUpStack = 0;
            }

            time += distance[targetPoint.row][targetPoint.col];
            return true;
        }
        return false;
    }
}

class Point {
    int row;
    int col;

    Point() {}

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