[SWEA] 모의 SW 역량 테스트 :: 2383번 점심 식사시간 (조합, 시뮬레이션)

sw expert academy 2383번 점심 식사시간 자바(java) 풀이

• 모의 SW 역량 테스트
• sw expert academy 2383번 점심 식사시간
  
  
  

문제정리

1. NxN 크기의 정사각형 방이 주어진다.
2. 1: 사람
   2~10: 계단의 입구이며 층계 수를 의미한다.
3. 이동 완료 시간: 모든 사람들이 계단을 내려가 아래 층으로 이동을 완료한 시간
4. 이동 시간: 계단 입구까지 가는데 걸리는 시간 + 계단을 내려가는 시간
5. 계단 입구까지 이동시간
   이동 시간(분) = | PR - SR | + | PC - SC |
   (PR, PC : 사람 P의 세로위치, 가로위치, SR, SC : 계단 입구 S의 세로위치, 가로위치)
6. 계단을 내려가는 시간
   계단을 내려가는 시간은 계단 입구에 도착한 후부터 계단을 완전히 내려갈 때까지의 시간이다.
   계단 입구에 도착하면, 1분 후 아래 칸으로 내려 갈 수 있다.
   계단 위에는 동시에 최대 3명까지만 올라가 있을 수 있다.
   이미 계단을 3명이 내려가고 있는 경우, 그 중 한 명이 계단을 완전히 내려갈 때까지 계단 입구에서 대기해야 한다.
   계단 1층 내려가는데 1분이 걸린다.
   => 이는 동시에 최대 3명까지만 계단을 내려갈 수 있음을 의미 합니다. 3명이 계단을 내려가고 있는데
   다른 사람이 그 계단에 도착하면 다른 사람이 모두 내려가서 계단 이용이 끝날때까지 기다려야 합니다.
7. 계단의 입구는 반드시 2개이다.

• 모든 사람들이 계단을 내려가 이동이 완료되는 최소 시간을 찾아라!
  
  
  

문제풀이

1. 사람들이 계단을 이용하는 조합을 모두 구합니다.
   사람이 5명이 있는 경우 다음과 같습니다.
   계단1/계단2
   0명/5명
   1명/4명
   2명/3명
   위와 같이 나누어지는 경우를 구하면 됩니다.
   5명/0명을 따로 구할 필요 없이 반대 계단을 이용하게 하면 모든 경우를 커버할 수 있습니다.

2. 계단과의 거리를 모두 구해놓습니다.

3. 거리를 감소시켜가며 0이 되면 계단 위에 도착한 것으로 판단합니다.
   dist=0 : 계단에 도착

    계단을 이용중인 사람이 3명 이하이면 dist를 -1로 하고 이용중임을 나타내게 함 -> 그 게단의 floor를 내려감
    3명보다 많으면 dist가 0인 채로 대기하다가 사람이 빠지면 그때 dist를 -1로 바꾸고 floor를 타고 내려간다.

   dist < 0 : 내려가고 있는 중
   dist > 0 : 계단에 아직 도착하지 못함

4. 계단에 도착한 뒤 계단을 이용중인 사람 수가 3명이하 이면 계단을 이용하고 계단을 하나씩 내려갑니다.

5. 계단에 다 도착한 사람 수를 count하며 모두 다 내려온 경우 그때 걸린 시간을 구합니다.
   이때 계단에 도착하고 1분 동안 기다린뒤 내려갈 수 있으므로 1분을 더 더합니다.

6. 이렇게 시간을 구하여 최소값가 비교하여 작다면 update 해줍니다.
   
   
   

점심 식사시간 자바 코드

좀더 자세한 내용들은 주석으로 달아두었으니 참고하시기 바랍니다!

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.Queue;
import java.util.ArrayList;
import java.util.LinkedList;

class Pos{
    int x;
    int y;
    int on;
    int floor;

    Pos(int x, int y){
        this.x = x;
        this.y = y;
    }

    Pos(int x, int y, int floor, int on){
        this.x = x;
        this.y = y;
        this.floor = floor;
        this.on = on;
    }
}

class Solution {
    static int min;
    static int N;
    static ArrayList<Pos> persons;
    static ArrayList<Pos> stairs;
    static boolean[] visited;
    static int[] floors;
    static boolean[] checks;

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int testNum = Integer.parseInt(br.readLine());

        for(int test=1; test<=testNum; test++){
            N = Integer.parseInt(br.readLine());
            persons = new ArrayList<>();
            stairs = new ArrayList<>();

            for(int i=0; i<N; i++){
                String[] temp = br.readLine().split(" ");
                for(int j=0; j<N; j++){
                    int t = Integer.parseInt(temp[j]);
                    if(t == 1)
                        persons.add(new Pos(i,j));
                    else if( t >= 1)
                        stairs.add(new Pos(i, j, t, 0));
                }
            }

            min = Integer.MAX_VALUE;
            for(int i=0; i<=persons.size()/2; i++){
                visited = new boolean[persons.size()];
                comb(0,i,persons.size());
            }

            System.out.println("#" + test + " " + min);
        }
        br.close();
    }

    public static void comb(int start, int r, int num){
        if(r == 0){
            // 선택한 계단과의 거리 구하기
            ArrayList<Integer> dist = new ArrayList<>();
            ArrayList<Integer> dist2 = new ArrayList<>();
            boolean[] visited2 = new boolean[num];

            // 계단과의 거리 구하기
            for(int i=0; i<num; i++){
                visited2[i] = !visited[i];
                if(visited[i]){
                    dist.add(Math.abs(persons.get(i).x - stairs.get(0).x) + Math.abs(persons.get(i).y - stairs.get(0).y));
                    dist2.add(Math.abs(persons.get(i).x - stairs.get(1).x) + Math.abs(persons.get(i).y - stairs.get(1).y));
                }
                else{
                    dist.add(Math.abs(persons.get(i).x - stairs.get(1).x) + Math.abs(persons.get(i).y - stairs.get(1).y));
                    dist2.add(Math.abs(persons.get(i).x - stairs.get(0).x) + Math.abs(persons.get(i).y - stairs.get(0).y));
                }
            }

            // 계단으로 움직이기
            int time = move(dist, num, visited);
            min = min > time ? time : min;

            // 계단을 반대로 이용하기
            time = move(dist2, num, visited2);
            min = min > time ? time : min;

            return;
        }
        for(int i=start; i<num; i++){
            visited[i] = true;
            comb(i+1, r-1, num);
            visited[i] = false;
        }
    }

    public static int move(ArrayList<Integer> dist, int num, boolean[] visited){
        int cnt = 0;
        int time = 0;

        // 계단을 이용중인 사람 관리
        // queue의 크기가 계단을 이용중인 사람 수를 나타낸다.
        Queue<Integer> q[] = new LinkedList[2];
        q[0] = new LinkedList<>();  // 첫 번째 계단 이용
        q[1] = new LinkedList<>();  // 두 번째 계단 이용

        while(true){
            // 모두 아래층에 도착한 경우 탈출
            if(cnt == num)
                break;
            // 거리를 감소시키며 계단으로 이동 시키기
            for(int i=0; i<num; i++){
                // 계단을 내려가고 있는 중
                if(dist.get(i) < 0)
                    continue;
                // 계단에 도착한 경우
                if(dist.get(i) == 0){
                    if(visited[i]){
                        if(q[0].size() < 3){
                            dist.set(i, -1);
                            q[0].offer(stairs.get(0).floor);
                        }

                    }
                    else{
                        if(q[1].size() < 3){
                            dist.set(i, -1);
                            q[1].offer(stairs.get(1).floor);
                        }
                    }
                    // 계단에 이미 도착하였기 때문에 거리를 줄이지 않고(움직이지 않고) continue
                    continue;
                }
                dist.set(i, dist.get(i) - 1);
            }

            // 계단에 있는 사람들 이동시키기
            for(int i=0; i<2; i++){
                int size = q[i].size();
                for(int j=0; j<size; j++){
                    int floor = q[i].poll();
                    // 내려가야 하는 계단 수가 1이상이면 내려감
                    if(floor > 1)
                        q[i].offer(floor-1);
                    else
                        // 다 내려왔으면 count 처리
                        cnt++;
                }
            }
            time++;
        }
        return time+1;
    }
}