[알고리즘][X] 코드트리 빵

https://www.codetree.ai/training-field/frequent-problems/problems/codetree-mon-bread/description?page=1&pageSize=20

import java.awt.Point;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

    static class Node {

        Point point;
        List<Point> history;

        public Node(Point point) {
            this.point = point;
            this.history = new ArrayList<>();
        }

        public Node(Point point, List<Point> history) {
            this.point = point;
            this.history = history;
        }
    }

    static int n;
    static int m;
    static int[][] map;
    static boolean[][] cantPass;
    static Point[] move;
    static Point[] conv;
    static int cnt;
    public static void main(String[] args) throws IOException {
        /**
         * 유의할 점
         * - 격자에 있는 모든 사람들이 움직이고 난 후 편의점을 지날 수 없게 된다.
         * - 한 칸에는 두 명의 사람이 있을 수 있다.
         * - 사람들이 목표로 하는 편의점은 모두 다르다.
         * - 누군가 들어온 적이 있는 베이스캠프라도 다른 사람이 거기서 출발할 수 있다.
         * - 다만 지나갈 수는 없다.
         * - t초에 모든 사람이 이동을 하고 난 후 편의점이나 베이스캠프를 지나갈 수가 없게 된다.
         *
         *
         * 필요한 정보
         * - 지나갈 수 있는 곳인지(편의점, 베이스캠프)
         * - 몇 사람이 도착했는지
         * - 지금 사람이 어디 위치에 있는지
         * - 지금 누가 이동할 수 있는지
         *
         * 시간이 t<=m을 만족하면 t번째 사람이 베이스캠프에 들어간다.
         */

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());

        map = new int[n + 1][n + 1];
        for (int i = 1; i <= n; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 1; j <= n; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
                if (map[i][j] == 1) {
                    map[i][j] = -1;
                }
            }
        }

        cnt = 0;
        Queue<Point> queue = new ArrayDeque<>();
        conv = new Point[m + 1];
        // 0은 빈 공간 1은 베이스캠프
        for (int i = 1; i <= m; i++) {
            st = new StringTokenizer(br.readLine());
            Point point = new Point(Integer.parseInt(st.nextToken()),
                    Integer.parseInt(st.nextToken()));
            queue.add(point);
            conv[i] = new Point(point);
            map[point.x][point.y] = i;
        }

//        print();
        cantPass = new boolean[n+1][n+1];
        move = new Point[m+1];
        int time = 0;
        while (true) {
            time++;
//            System.out.println(time);
            // 각각의 사람 움직이기
            movePeople(move);

            // 도착한 편의점 찾고 사람 없애주기
            List<Point> arrived = findArrival();
            // 도착한 편의점은 못 지나가게 만들기
            for (Point point : arrived) {
                cantPass[point.x][point.y] = true;
                cnt++;
            }

            // 베이스캠프로 들어가기
            if (!queue.isEmpty()) {
                Point cur = queue.poll();
                Point base = findBase(cur);
//                System.out.println("base = " + base);
                move[time] = base;
                // 베이스캠프 못지나가게 막아주기
                cantPass[base.x][base.y] = true;
            }
            if (cnt == m) {
                break;
            }
        }

        System.out.println(time);
    }

    private static void print() {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                System.out.print(map[i][j] + " ");
            }
            System.out.println();
        }
        System.out.println();
    }
    private static void movePeople(Point[] move) {
        // 지나갈 수 없는 곳 고려
        // 최단거리에 따라 움직임
        // 최단거리가 여러 곳이라면 상좌우하 순
        // 어디로 이동해야할지 파악하면 정확히 한칸만 이동해주어야 함
        for (int i = 1; i <= m; i++) {
            if (move[i] == null) {
                continue;
            }
            move[i] = bfs(move[i], i).get(0);
        }
    }

    private static List<Point> bfs(Point start, int id) {
        int[] dx = {-1, 0, 0, 1};
        int[] dy = {0, -1, 1, 0};
        boolean[][] visited = new boolean[n+1][n+1];
        Queue<Node> queue = new ArrayDeque<>();
        queue.add(new Node(start));
        visited[start.x][start.y] = true;
        while (!queue.isEmpty()) {
            Node cur = queue.poll();
            Point point = cur.point;
            List<Point> history = cur.history;
            if (map[point.x][point.y] == id) {
                return history;
            }
            for (int i = 0; i < 4; i++) {
                int nx = point.x + dx[i];
                int ny = point.y + dy[i];

                if (1 <= nx && nx <= n && 1 <= ny && ny <= n && !visited[nx][ny]) {
                    if (!cantPass[nx][ny]) {
                        visited[nx][ny] = true;
                        List<Point> newHis = new ArrayList<>();
                        newHis.addAll(history);
                        newHis.add(new Point(nx, ny));
//                        if (newHis.size() == 0) {
//                            newHis.add(new Point(nx, ny));
//                        }
                        queue.add(new Node(new Point(nx, ny), newHis));
                    }
                }
            }
        }
        return null;
    }

    private static List<Point> findArrival() {
        List<Point> result = new ArrayList<>();
        for (int i = 1; i <= m; i++) {
            if (move[i] == null) {
                continue;
            }
            if (move[i].equals(conv[i])) {
//                System.out.println(move[i]);
                result.add(new Point(move[i]));
                move[i] = null;
            }
        }
        return result;
    }

    private static Point findBase(Point start) {
        int[] dx = {-1, 0, 0, 1};
        int[] dy = {0, -1, 1, 0};
        boolean[][] visited = new boolean[n+1][n+1];
        Queue<Point> queue = new ArrayDeque<>();
        queue.add(start);
        visited[start.x][start.y] = true;
        while (!queue.isEmpty()) {
            Point point = queue.poll();

            if (map[point.x][point.y] == -1) {
                return point;
            }
            for (int i = 0; i < 4; i++) {
                int nx = point.x + dx[i];
                int ny = point.y + dy[i];

                if (1 <= nx && nx <= n && 1 <= ny && ny <= n && !visited[nx][ny]) {
                    if (!cantPass[nx][ny]) {
                        visited[nx][ny] = true;
                        queue.add(new Point(nx, ny));
                    }
                }
            }
        }
        return null;
    }
}

나의 풀이

- m을 써야하는데 n을 써서 틀렸다. 정말 조심하자!!!