[SWEA] 2383. 점심식사 시간

문제 보기 >> [SWEA] 2383. 점심식사 시간

1. 입력을 받을때 사람의 위치와 계단의 위치를 각각의 ArrayList에 저장.

2. whichStair(int len) 메소드 - 중복순열

각각의 사람이 어떤 계단을 이용할 것인지 중복순열 코드를 돌려서 모든 케이스를 다 확인할 수 있게 한다.

중복순열이 완성되면, 우선순위큐에 데이터를 add.

우선순위 큐의 타입으로 pair2 클래스를 선언해서 사용했다.

**pair2 클래스

각 사람에 대해 할당된 시간과 이용할 계단, 그리고 상태를 저장하기 위한 클래스.

status ==> -1 : 계단에 도착하기 전 // 0 : 계단에 도착은 했지만 대기중. // 1 : 계단에 올라가 있음.  

하단 pair2 클래스 선언 부분에서 Compare부분을 보면, 기본적으로 시간이 짧은 순으로 정렬되고 시간이 같을땐 status를 기준으로 정렬했다. 

이 compare는 우선순위큐에서 정렬되는 기준을 정하기 위함이다.

같은 시간내에서 계단에 올라가 있는 사람을 먼저 pop 하기위해서 시간이 같을때에는, status가 큰 수를 우선적으로 정렬되도록 했다.

3. goStair() 메소드

각각의 사람이 어떤 계단을 사용할것인지 완성이 되었다면, goStair() 메소드에서 실제로 계단에 보내본다.

inStair 배열은 각각의 계단을 몇명의 사람이 이용하고 있는지 카운트해주는 배열이다.

우선순위큐(pq)에서 시간이 짧은사람(계단에 있는사람->대기->도착 순으로 pop) 부터 확인해본다.

가장 바깥 while문은 시간에 대한 while문이다 min이 1씩 증가한다.

min이 일정 시간일때 안쪽 while을 돌면서 해당 시간인 사람을 pop 해서 검사한다.

status 가 1이 아니면 아직 계단을 이용하지 못한 사람이고, 그 중 -1이면 이제 계단에 도착한 사람이므로 계단 이용전 필수 대기시간인 +1을 더 해준다.

시간과 상태를 갱신해 다시 pq에 add해주고 계단이용자수를 증가시켜준다.

** 여기서 ntime이 의미하는 것은 시작점부터 계단까지 시간 + 대기시간 + 계단 이용시간이다.

즉, 계단 이용이 끝날때까지는 큐에서 나올 수 없다.

만약 계단이 포화상태라 갈수 없다면 시간만 +1 해주고, status는 0으로 다시 add한다.

status가 1이면 계단에 올라있는 상태에서 시간이 다 지난것을 의미하기 떄문에 해당 inStair을 감소시켜주고 큐에 다시 add 하지 않는다.

4. q가 비게되면 최소값을 갱신해준다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
 
//SWEA :: 2383 점심 식사시간 
//2019-04-04
public class Solution2383_점심식사시간 {
    private static int[][] map;
    private static int N, ans;
    private static ArrayList<pair> ppl;
    private static ArrayList<pair> stair;
    private static int[] set;
    private static PriorityQueue<pair2> pq;
 
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
 
        for (int tc = 1; tc <= T; tc++) {
            N = Integer.parseInt(br.readLine());
            map = new int[N][N];
            ppl = new ArrayList<>();
            stair = new ArrayList<>();
            for (int i = 0; i < N; i++) {
                StringTokenizer st = new StringTokenizer(br.readLine(), " ");
                for (int j = 0; j < N; j++) {
                    map[i][j] = Integer.parseInt(st.nextToken());
                    if (map[i][j] == 1)
                        ppl.add(new pair(i, j));
                    if (map[i][j] > 1)
                        stair.add(new pair(i, j));
                }
            } /// input
            set = new int[ppl.size()];
            ans = Integer.MAX_VALUE;
            whichStair(0);
 
            System.out.println("#" + tc + " " + ans);
        } // end of tc
    }// end of main
 
    public static void whichStair(int len) {
        if (len == ppl.size()) { // 사람의 명수만큼 계단 고르기 --> 중복순열
            // System.out.println(Arrays.toString(set));
            pq = new PriorityQueue<>();
            
            for (int i = 0; i < len; i++) {
                int py = ppl.get(i).y;
                int px = ppl.get(i).x;
                int sy = stair.get(set[i]).y;
                int sx = stair.get(set[i]).x;
                int t = Math.abs(py - sy) + Math.abs(px - sx);
                pq.add(new pair2(t, set[i], -1));
            }
            goStair();
            return;
        }
 
        for (int i = 0; i < stair.size(); i++) {
            set[len] = i; // 인덱스 저장
            whichStair(len + 1);
        }
    } // end of whichStair
 
    public static void goStair() {
        /*
         * pair2의 status -1: 계단에 도착 전 0: 계단에 도착은 했지만 대기중. 1:계단에 올라가 있음
         */
        int min = 0;
        int[] inStair = new int[stair.size()]; // idx번째 계단에 몇명의 사람이 있는지 확인.
        while (!pq.isEmpty()) {
            min++;
 
            while (!pq.isEmpty()) {
                pair2 front = pq.peek();
                if (front.time != min)
                    break;
                pq.poll();
                int mystair = front.stair;
                if (front.status != 1) { // 계단 아직 안감.
                    //계단을 내려갈 수 있나?
                    if (inStair[mystair] < 3) { // 갈 수 있으면
                        int ntime = 0;
                        if (front.status == -1) { //계단에 최초 도착이면 1분 대기한다.
                            ntime = front.time + 1 + map[stair.get(mystair).y][stair.get(mystair).x];
                        } else if (front.status == 0) { //이전에 도착해 대기하고있었으면 바로 계단에 간다.
                            ntime = front.time + map[stair.get(mystair).y][stair.get(mystair).x];
                        }
                        pq.add(new pair2(ntime, front.stair, 1));
                        inStair[mystair]++;
                    } else { // 계단이 포화 상태라 갈 수 없다면.
                        pq.add(new pair2(front.time + 1, front.stair, 0));
                    }
                } else { // front.status == 1//계단에 있는 상태.
                    inStair[mystair]--;
                }
            }
        }
        ans = ans > min ? min : ans;
    }
 
    static class pair {
        int y;
        int x;
 
        public pair(int y, int x) {
            super();
            this.y = y;
            this.x = x;
        }
    } // end of pair
 
    static class pair2 implements Comparable<pair2> {
        int time;
        int stair;
        int status;
 
        public pair2(int time, int stair, int status) {
            super();
            this.time = time;
            this.stair = stair;
            this.status = status;
        }
 
        @Override
        public int compareTo(pair2 o) {
            // TODO Auto-generated method stub
            if (this.time == o.time) {
                return o.status - this.status;
            } else {
                return this.time - o.time;
            }
        }
 
    }
}// end of class