[Code Tree] 코드트리 빵(Java)

문제

https://www.codetree.ai/training-field/frequent-problems?page=3&pageSize=20

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

풀이

[자료 구조]

- int[][] DELTAS: 사방 이동 좌표

- PriorityQueue<int[]> NEXT_MOVES: 사람이 편의점을 향해 가는 다음 위치

    - 이동 수 기준 오름차순 정렬

- PriorityQueue<int[]> MOVES: 편의점에서 베이스캠프까지의 움직임

    - 이동 수 기준 오름차순 정렬 > 이동 수 같으면 행 기준 오름차순 정렬 > 행 같으면 열 기준 오름차순 정렬

- int[][] map: 베이스 캠프의 정보와 베이스 캠프 및 편의점의 방문 여부

    - 베이스 캠프 = 1

    - 더이상 방문 불가 지역: =음수(해당 지역에 방문한 사람 번호의 음수)

- int[][] convenienceStores: 편의점의 위치

    - convenienceStores[i] = i번재 사람이 가고자 하는 편의점 좌표

- boolean[][] isVisited: 편의점에서 베이스캠프까지의 최단 경로를 구하기 위한 방문 여부

- PriorityQueue<int[]>[] people: 사람들의 이동 위치

    - 이동 수 기준 오름차순 정렬

 

[풀이]

- m명의 사람이 모두 편의점에 도착할 때까지 아래 과정 반복한다.

    1. 편의점을 향해 이동

        - people의 각 요소를 탐색하며, 이동 가능하면(people[i]가 비어있지 않으면) 사방 중 범위 내에 있으면서 방문 가능한(map[x][y] >= 0) 위치를 NEXT_MOVES에 추가

        - 사방 탐색 중 편의점에 도착하면 arrive를 증가시키고, map[x][y]을 -i로 초기화. 더이상 사람이 이동을 하면 안되므로 people[i]와 NEXT_MOVES를 모두 초기화시킨다.

        - 편의점에 도착하지 못하면 NEXT_MOVES를 people[i]에 모두 추가한 후 초기화시킨다.

    2. time <= m이면, 베이스캠프로 이동

        - time번째 사람이 가고자 하는 편의점의 x, y 좌표와 이동 수 0을 원소로 갖는 int[]를 MOVES에 삽입한다.

        - 방문체크를 위한 isVisited를 false로 초기화시킨다.

        - 베이스 캠프에 도착할 때까지 범위 내에 있으면서(x >= 0 && x < n && y >= 0 && y < n) 한 번도 방문하지 않았고(!isVisited[x][y]), 방문이 가능한(map[x][y] >= 0) 곳을 MOVES에 추가하고, 방문 처리해준다.

        - 베이스 캠프에 도착하면 map[x][y]를 -i로 초기화 시키고, 현재 위치의 x, y 좌표와 이동 수 0을 원소로 갖는 int[]를 people[i]에 삽입하고, MOVES를 초기화시킨다.

- m명이 모두 도착하면 time을 출력한다.

소스 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {

    private static final int[][] DELTAS = {{-1, 0}, {0, -1}, {0, 1}, {1, 0}};
    private static final int EMPTY = 0;
    private static final int BASECAMP = 1;
    private static final int MOVE = 2;
    private static final PriorityQueue<int[]> NEXT_MOVES = new PriorityQueue<>(Comparator.comparing(person -> person[MOVE]));
    private static final PriorityQueue<int[]> MOVES = new PriorityQueue<>((p1, p2) -> {
        if (p1[MOVE] == p2[MOVE]) {
            if (p1[0] == p2[0]) {
                return p1[1] - p2[1];
            }
            return p1[0] - p2[0];
        }
        return p1[MOVE] - p2[MOVE];
    });

    private static int[][] map;
    private static int[][] convenienceStores;
    private static boolean[][] isVisited;
    private static PriorityQueue<int[]>[] people;
    private static int n;
    private static int m;
    private static int arrive;

    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer stringTokenizer = new StringTokenizer(bufferedReader.readLine());
        n = Integer.parseInt(stringTokenizer.nextToken());
        m = Integer.parseInt(stringTokenizer.nextToken());
        map = new int[n][n];
        isVisited = new boolean[n][n];
        for (int i = 0; i < n; i++) {
            stringTokenizer = new StringTokenizer(bufferedReader.readLine());
            for (int j = 0; j < n; j++) {
                map[i][j] = Integer.parseInt(stringTokenizer.nextToken());
            }
        }
        convenienceStores = new int[m + 1][2];
        people = new PriorityQueue[m + 1];
        for (int i = 1; i <= m; i++) {
            stringTokenizer = new StringTokenizer(bufferedReader.readLine());
            convenienceStores[i][0] = Integer.parseInt(stringTokenizer.nextToken()) - 1;
            convenienceStores[i][1] = Integer.parseInt(stringTokenizer.nextToken()) - 1;
            people[i] = new PriorityQueue<>(Comparator.comparing(person -> person[MOVE]));
        }
        int time = 0;
        while (arrive < m) {
            time++;
            moveToConvenienceStore();
            if (time <= m) {
                moveToBasecamp(time);
            }
        }
        System.out.println(time);
    }

    private static void moveToConvenienceStore() {
        for (int i = 1; i <= m; i++) {
            while (!people[i].isEmpty()) {
                int[] current = people[i].poll();
                int x = current[0];
                int y = current[1];
                for (int[] delta : DELTAS) {
                    int dx = x + delta[0];
                    int dy = y + delta[1];
                    if (isInRange(dx, dy) && map[dx][dy] >= EMPTY) {
                        if (convenienceStores[i][0] == dx && convenienceStores[i][1] == dy) {
                            arrive++;
                            map[dx][dy] = -i;
                            people[i].clear();
                            NEXT_MOVES.clear();
                            break;
                        }
                        NEXT_MOVES.offer(new int[]{dx, dy, current[MOVE] + 1});
                    }
                }
            }
            people[i].addAll(NEXT_MOVES);
            NEXT_MOVES.clear();
        }
    }

    private static void moveToBasecamp(int time) {
        MOVES.offer(new int[]{convenienceStores[time][0], convenienceStores[time][1], 0});
        for (int i = 0; i < n; i++) {
            Arrays.fill(isVisited[i], false);
        }
        while (!MOVES.isEmpty()) {
            int[] current = MOVES.poll();
            int x = current[0];
            int y = current[1];
            if (map[x][y] == BASECAMP) {
                map[x][y] = -time;
                people[time].offer(new int[]{x, y, 0});
                MOVES.clear();
                return;
            }
            for (int[] delta : DELTAS) {
                int dx = x + delta[0];
                int dy = y + delta[1];
                if (isInRange(dx, dy) && !isVisited[dx][dy] && map[dx][dy] >= EMPTY) {
                    isVisited[dx][dy] = true;
                    MOVES.offer(new int[]{dx, dy, current[MOVE] + 1});
                }
            }
        }
    }

    private static boolean isInRange(int dx, int dy) {
        return dx >= 0 && dx < n && dy >= 0 && dy < n;
    }
}