[SW Expert] 2383. [모의 SW 역량테스트] 점심 식사시간

생각

점심 시간에 사람들이 점심을 먹으러 계단을 내려가려고 한다.
계단이 2개 주어져있고 각각의 계단은 최대 3명만 이용이 가능하며, 3명이 계단을 내려가는 중일경우
도착한 사람은 계단입구에서 대기를 하고 있는다.
계단은 도착하자 마자 내려가지 못하고, 도착한 1분 후 부터 내려갈 수 있다.
사람은 1로 주어지고, 계단은 2~10으로 주어지며 2~10은 계단을 내려가는데 걸리는 시간을 의미한다.
사람과 계단의 상태가 주어질 때, 최소로 걸리는 시간을 구하시오.

처음 생각

처음 문제를 봤을 때, 이걸 어떻게 구하지?? 라는 생각이 앞섰다. 문제를 찬찬히 읽어보니 가장 결정적인 힌트는 사람이 최대 10명이고, 계단은 무조건 2개라는 것이다. 따라서 계단을 편의상 1번,2번 이라고 하였을 때 사람들이 1번 2번을 이용하는 모든 경우의 수를 완전 탐색을 이용하여 진행하였다.

다음 생각

DFS를 통해 각 사람이 1번 계단으로 갈지 2번 계단으로 갈지의 모든 경우를 정해준 후, 정해진 정보를 가지고 Queue를 이용해서 완전 탐색을 하였다.

다다음 생각

모든 경우를 구해주는 것이기 때문에 주어진 조건만 잘 구현해 주면 된다. inner class로 만들어준 Pair에서 time으로 각각 시간대를 관리해주었고 Queue에 넣기 전에 정해진 계단과의 거리(dist)를 구해서 미리 넣어주었다.

▶ 거리가 짧은 사람들을 먼저 계단으로 보내주기 위해서 PriorityQueue를 이용하였다. 왜냐면 dist와 time을 이용해서 계단에 도착하는 것은 짧은 사람들이 먼저 도착하지만 계단에서 빠져나가는 것도 먼저 실행을 해줘야 뒤의 Queue에서 계단에 들어 갈 수 있기 때문이다. 처음에 일반 Queue로 만들었을 때는 제출시 48/50이 나와 PriorityQueue로 수정한 뒤 PASS 하였다.

방안

1) 이동을 시킬 때 무언가 순서가 조금이라도 있어야 한다면 PriorityQueue를 이용하면 좋은 것 같다.

2) 문제가 곧 답이므로 문제에서 힌트를 얻자!!

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141

import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.Comparator; import java.util.List; import java.util.PriorityQueue; import java.util.StringTokenizer;   class Solution {     static int n;     static Door[] door;     static int[][] arr;     static List<Pair> list;     public static void main(String[] args) throws IOException{         BufferedReader br = new BufferedReader(new InputStreamReader(System.in));         list = new ArrayList<>();         int tc = Integer.parseInt(br.readLine());         StringBuilder sb = new StringBuilder();         for(int i=1;i<=tc;i++) {             n = Integer.parseInt(br.readLine());             list.clear();             door = new Door[2];             arr = new int[n][n];             for(int j=0;j<n;j++) {                 StringTokenizer st = new StringTokenizer(br.readLine());                 for(int k=0;k<n;k++) {                     arr[j][k] = Integer.parseInt(st.nextToken());                      if(arr[j][k]==1) list.add(new Pair(j, k, 0, 0, 0,0,0));                     else if(arr[j][k]>=2) {                         if(door[0]==null) door[0] = new Door(j, k, arr[j][k]);                         else door[1] = new Door(j, k, arr[j][k]);                     }                 }             }             // 계단이 2개 뿐이니 완전탐색을 하자.             visited = new boolean[list.size()];             // 부분 집합 만들어 주기             min = Integer.MAX_VALUE;             dfs(0);             solve();             sb.append("#"+i+" "+min+"\n");         }         System.out.print(sb);     }       static boolean[] visited;     private static void dfs(int idx) {         if(idx==list.size()) {             solve();             return;         }         // 1번 타겟         visited[idx] = true;         dfs(idx+1);         visited[idx] = false;         // 2번 타겟         dfs(idx+1);     }          static int min;     static int[][] dir = {{1,0},{0,1},{-1,0},{0,-1}};     private static void solve() {         PriorityQueue<Pair> queue = new PriorityQueue<>(new Comparator<Pair>() {             @Override             public int compare(Pair o1, Pair o2) {                 if(o1.time>o2.time) return 1;                 else if(o1.time==o2.time) {                     if(o1.dist>o2.dist) return 1;                     else if(o1.dist==o2.dist) return 0;                     else return -1;                 }else return -1;             }         });         // 계단 번호 2~10 계단은 반드시 2개, 사람은 1~최대 10명         for(int i=0;i<list.size();i++) {             Pair t = list.get(i);             // 해당 출구와 거리계산             int dist = 0;             // true면 1번 출구, 2번 출구 나누기             if(visited[i]) {                 dist = Math.abs(t.x-door[0].x)+Math.abs(t.y-door[0].y);                 queue.add(new Pair(t.x, t.y, 0, 0, dist,0,0));             }else {                 dist = Math.abs(t.x-door[1].x)+Math.abs(t.y-door[1].y);                 queue.add(new Pair(t.x, t.y, 1, 0, dist,0,0));             }         }         int time = 0;         int[] dCnt = new int[2];         while(!queue.isEmpty()) {             Pair t = queue.poll();             time = t.time;             // 해당 계단에 아직 도달 안했다면 다시 넣어주고 다음꺼.(계단에 도달후 한 번 대기까지)             if(t.dist>=time) {                 queue.add(new Pair(t.x, t.y, t.gate,t.wait,t.dist,t.time+1,t.c));                 continue;             }             // 계단 내려가는 중             if(t.wait!=0) {                 if(t.wait==door[t.gate].n) {                     dCnt[t.gate]--;                     continue;                 }                 queue.add(new Pair(t.x, t.y, t.gate,t.wait+1,t.dist,t.time+1,t.c));                 continue;             }             // 해당 계단이 꽉차있다면 대기             if(dCnt[t.gate]==3) {                 queue.add(new Pair(t.x, t.y, t.gate,t.wait,t.dist,t.time+1,t.c));             }else {                 // 아니라면 들어가서 wait 해당 n 만큼 wait 늘리기                 dCnt[t.gate]++;                 queue.add(new Pair(t.x, t.y, t.gate,t.wait+1,t.dist,t.time+1,t.c));             }         }         min = Math.min(min, time);     }          static class Door{         private int x,y,n;         public Door(int x,int y,int n) {             this.x = x;             this.y = y;             this.n = n;         }     }          static class Pair{         private int x,y,gate,wait,dist,time,c;         public Pair(int x,int y,int gate,int wait,int dist,int time,int c) {             this.x = x;             this.y = y;             this.gate = gate;             this.wait = wait;             this.dist = dist;             this.time = time;             this.c = c;         }     } } Colored by Color Scripter

cs