[SWexpert] 2383. 점심 식사시간

우선, 삼성SW Expert 아카데미의 문제임을 밝힙니다.
문제 주소: Click!

 입력으로 사람의 위치와 계단(항상 2개)의 위치가 주어집니다.

사람들이 계단으로 이동하는데. 계단은 최대 3명만 들어갈 수 있습니다.

그리고 계단의 좌표에는 계단의 높이가 적혀있습니다.

1분에 1칸씩 내려갈 수 있고, 계단에 도착했다고 해서 바로 들어갈 수 있는게 아니고
1분을 기다려야합니다. ( 그래서 걸리는 시간을 계산할 때 미리 1을 더해서 두는 게 편합니다. )

저는 계단과 사람을 객체로 만들어서
계단에 사람이 들어간다는 생각으로 계단에 사람이 지나갈 수 있게 어레이 리스트를 만들고 3명이 꽉차면
들어온 순서대로 대기할 수 있도록 큐를 만들어 두었습니다.
ArrayList<Person> service;  // 계단에 들어온 사람들
Queue<Person> waiting;      // 대기중인 사람들
그리고 사람수와 지도의 크기가 10이하이므로 단순히 멱집합으로 접근해도 되겠다는 생각이 들었습니다
    public static void powerSet(int idx, int peopleCnt, ArrayList<Stair> stair, ArrayList<Person> people)
    {

        if(idx == peopleCnt)
        {
            // 4. 시뮬레이션 시작
             min = Math.min(min, go(stair, people));

            // 5. back-tracking: 사람리스트에 있는 사람객체의 정보들이 변경돼서 돌아오기 때문에 다시 초기화해준다.
            for(Person p : people)
            {
                p.isExit = false;
                p.height = 0;
            }
            return;
        }
        //1로 간 사람
         people.get(idx).is1st = true;
        powerSet(idx+1, peopleCnt, stair, people);
        //2로 간 사람
         people.get(idx).is1st = false;
        powerSet(idx+1, peopleCnt, stair, people);
    }

그리고 모든 경우의 수에서(사람수가 최대 10명이므로 최대 2^10 = 1024가지) 구하고 
거기에서 걸린시간이 최소인 값을 출력하도록 했습니다.
자세한 내용은 문서의 주석에 달아두었으며 디버깅에 유의하셔야 할 곳도 따로 메모를 해두었습니다.
도움이 되셨으면 좋겠습니다.
궁금한 점이나 개선할 사항이 보이신다면 댓글로 알려주세요~

import java.io.*;
import java.util.*;
 
public class Solution점심식사
{
    public static String src = "10\n5\n0 1 1 0 0\n0 0 1 0 3\n0 1 0 1 0\n0 0 0 0 0\n1 0 5 0 0\n5\n0 0 1 1 0\n0 0 1 0 2\n0 0 0 1 0\n0 1 0 0 0\n1 0 5 0 0\n6\n0 0 0 1 0 0\n0 0 0 0 0 0\n0 0 0 0 0 0\n0 1 0 0 0 0\n2 0 1 0 0 0\n0 0 2 0 0 0\n6\n0 0 0 0 0 0\n0 0 0 0 0 0\n0 0 0 0 0 0\n0 0 0 0 0 0\n1 0 0 0 0 0\n0 0 0 2 0 4\n7\n0 0 0 0 0 0 0\n0 0 0 0 0 0 4\n0 0 0 0 1 0 0\n1 0 0 1 0 0 0\n0 0 0 0 0 0 0\n0 0 0 0 0 0 0\n0 2 0 0 0 0 0\n7\n0 0 0 0 0 0 0\n7 0 0 0 0 0 0\n0 0 0 0 0 0 0\n0 0 0 0 0 0 0\n0 0 0 0 0 0 0\n2 0 0 0 0 1 0\n0 0 0 0 0 0 0\n8\n0 0 0 0 0 0 0 0\n0 0 0 0 0 0 0 2\n0 0 0 0 0 0 0 0\n2 0 0 0 0 0 0 0\n0 0 0 0 0 1 0 0\n0 0 0 0 0 0 0 0\n0 0 0 0 0 0 1 0\n0 0 0 0 1 0 0 0\n8\n3 0 0 0 0 0 5 0\n0 0 0 0 0 0 0 0\n1 0 0 0 0 0 0 0\n0 0 0 0 0 0 0 0\n1 0 1 1 0 0 0 0\n0 0 0 0 0 0 1 0\n0 0 0 0 0 0 0 0\n0 0 0 0 0 0 0 0\n9\n0 0 0 1 0 0 0 0 0\n0 1 0 0 0 0 0 0 0\n0 0 0 0 0 0 0 0 8\n7 0 0 0 0 1 0 0 0\n0 0 0 0 0 1 1 0 0\n0 0 0 0 0 0 0 0 0\n1 0 0 0 0 1 0 0 0\n0 0 0 0 0 0 0 0 0\n0 0 0 0 0 0 0 0 0\n10\n0 0 0 0 0 0 0 0 0 0\n0 0 0 0 1 0 0 0 0 0\n0 0 1 0 0 0 0 0 0 0\n0 0 0 0 0 0 0 0 0 0\n0 0 0 0 0 0 0 0 0 0\n3 0 1 0 1 0 0 0 0 2\n1 1 0 0 1 0 1 0 0 0\n0 0 0 0 0 0 0 0 0 0\n0 0 0 0 0 0 0 0 0 0\n0 0 0 0 0 0 0 0 0 0";
    public static int min;
    public static class Person
    {
        int num;                    // 디버깅용 사람번호
        int y,x;                    // 거리계산을 위한 좌표
        int height, dist1, dist2;   // 현재 몇 계단을 내려갔는지, 계단 1과2까지의 거리
        boolean is1st;              // 1번 계단을 선택했는지
        boolean isExit;             // 이미 점심먹으러 간 사람인지 체크
 
        Person(int num, int y, int x)
        {
            this.num = num;
            this.y = y;
            this.x = x;
            height = 0;
            isExit = false; is1st = false;
        }
        @Override
        public String toString()
        {
            return num+"번("+height+")";
        }
    }
    public static class Stair
    {
        int y,x,height;
        ArrayList<Person> service;  // 계단에 들어온 사람들
        Queue<Person> waiting;      // 대기중인 사람들
 
        Stair(int y, int x, int height)
        {
            this.y = y;
            this.x = x;
            this.height = height;
            service = new ArrayList<>();
            waiting = new LinkedList<>();
        }
        public boolean canService()
        {
            return service.size() < 3;
        }
    }
    public static void main(String[] args) throws Exception
    {
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        br = new BufferedReader(new StringReader(src));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st;
        int tc = Integer.parseInt(br.readLine());
        for (int t = 1; t <= tc; t++)
        {
            sb.append("#").append(t).append(" ");
            //////////////////////////////////////
            min = Integer.MAX_VALUE;
            int N = Integer.parseInt(br.readLine());
            int map[][] = new int[N][N];
            ArrayList<Stair> stair = new ArrayList<>();
            ArrayList<Person> people = new ArrayList<>();
 
            for (int i = 0; i < N; i++)
            {
                st = new StringTokenizer(br.readLine());
                for (int j = 0; j < N; j++)
                {
                    map[i][j] = Integer.parseInt(st.nextToken());
                    if(map[i][j] == 1)  // 사람일 경우
                    {
                        people.add(new Person(people.size()+1, i, j));
                    } else if(map[i][j] > 1)    // 계단일 경우
                    {
                        stair.add(new Stair(i, j, map[i][j]));
                    }
                }
            }
            //1. 사람객체에 각 계단까지의 거리를 업데이트 한다.
            Stair first = stair.get(0);
            Stair second = stair.get(1);
            for (Person p : people)
            {
                // 계단과의 좌표 차이 + 1 (<- 1은 대기시간이다.)
                p.dist1 = Math.abs(p.y - first.y) + Math.abs(p.x - first.x) + 1;
                p.dist2 = Math.abs(p.y - second.y) + Math.abs(p.x - second.x) + 1;
            }
            //2. 멱집합을 통해 가능한 경우의 수를 계산한다.
            powerSet(0, people.size(), stair, people);
            sb.append(min);
            //////////////////////////////////////
            sb.append("\n");
        }
        bw.write(sb.toString());
        bw.flush();
    }
 
    // 3. 멱집합을 통해 가능한 모든 부분집합을 구한다.
    public static void powerSet(int idx, int peopleCnt, ArrayList<Stair> stair, ArrayList<Person> people)
    {
        if(idx == peopleCnt)
        {
            // 4. 시뮬레이션 시작
            min = Math.min(min, go(stair, people));
 
            // 5. back-tracking: 사람리스트에 있는 사람객체의 정보들이 변경돼서 돌아오기 때문에 다시 초기화해준다.
            for(Person p : people)
            {
                p.isExit = false;
                p.height = 0;
            }
            return;
        }
        //1로 간 사람
        people.get(idx).is1st = true;
        powerSet(idx+1, peopleCnt, stair, people);
        //2로 간 사람
        people.get(idx).is1st = false;
        powerSet(idx+1, peopleCnt, stair, people);
    }
 
    // 모든 사람들이 계단을 통과할 때까지의 시간을 반환한다.
    public static int go(ArrayList<Stair> stairs, ArrayList<Person> people)
    {
        int time = 0;                   // 0초부터 세기 시작
        Stair first = stairs.get(0);    // 첫 번째 계단
        Stair second = stairs.get(1);   // 두 번째 계단
 
        int people_cnt = people.size(); // 사람수
        while(people_cnt > 0)           // while문이 한바퀴 돌 때마다 시간이 1분씩 흐른다.
        {
            // 1.사람객체에는
            for(Person p : people)
            {
                if(p.isExit) continue; // isExit가 있어서 이미 점심 먹으러 나간 사람은 건너 뛴다.
                if(p.is1st)            // 아직 점심을 못 먹으러 간 사람들 중 1번 계단을 선택한 사람중
                {
                    if(p.dist1 != time) continue; // 도착하지 못한 사람은 건너 뛰고
                    if(!first.canService())       // 왔는데, 계단이 꽉차 있으면 대기열에 들어간다.
                        first.waiting.add(p);
                    else                          // 아니면 계단에 들어간다.
                        first.service.add(p);
                }
                else                   // 2번 계단을 선택한 경우, 이하 동일.
                {
                    if(p.dist2 != time) continue;
                    if(!second.canService())
                        second.waiting.add(p);
                    else
                        second.service.add(p);
                }
            }
 
            // 2.[현재]계단에 있는 사람들을을 한칸씩 내려보낸다.
            for(int i = 0; i < first.service.size(); i++)
                first.service.get(i).height++;  // 사람객체의 height는 자신이 올라간 계단의 높이이다.
            for(int i = 0; i < second.service.size(); i++)
                second.service.get(i).height++; // 나중에 이 높이가 계단의 높이와 같아지면 탈출!
 
            // 3. 계단을 다 내려간 사람들이 점심을 먹을 수 있게 도와주자 : 이쪽을 디버깅을 유심히 해볼것.
            for (int i = 0; i < first.service.size(); i++)
            {
                Person sp = first.service.get(i);   // 계단에 있는 사람이
                if(sp.height == first.height)       // 계단을 다 내려간 경우
                {
                    sp.isExit = true;               // 다음 번을 위해 나갔다고 표시를 하고
                    first.service.remove(sp);       // 서비스 리스트에서 제거한다.
                    people_cnt--;                   // 처리해야할 사람 수도 감소시키고
                    i--;                            // 계단을 통과한 사람을 내보내면(리스트에서 삭제하면)
                                                    // 리스트의 구현특성상 남아있던 원소들이 앞으로 한 칸씩 자동으로 당겨진다.
                                                    // 반면, i는 계속 1씩 증가하고 있기 때문에. 삭제시 i도 증가해버리면
                                                    // i번째로 당겨진 원소를 읽지 못 하게 된다. 그래서 삭제시에는 i를 하나 감소시켜야 한다.
                }
            } // 계단 2의 경우도 이하 동일
            for (int i = 0; i < second.service.size(); i++)
            {
                Person sp = second.service.get(i);
                if(sp.height == second.height)
                {
                    sp.isExit = true;
                    second.service.remove(sp);
                    people_cnt--;
                    i--;
                }
            }
 
            // 4. 계단에 여유가 있으면서 대기열(큐)에 사람이 있을 경우
            while(first.canService() && first.waiting.size() > 0)
            {
                Person waitP = first.waiting.poll();    // 대기큐에서 사람을 꺼내고
                first.service.add(waitP);               // 서비스 리스트에 넣는다.
            }
            while(second.canService() && second.waiting.size() > 0)
            {
                Person waitP = second.waiting.poll();
                second.service.add(waitP);
            }
 
            // 5. 1분을 흐르게 한다.
            time++;
        }
 
        // 6. 사람들이 모두 탈출했다! 걸린 시간을 반환해주자.
        return time;
    }
}