SWEA[2383] - 점심 식사시간

링크

SWEA[2383]

문제설명

• 완전탐색 + 시뮬레이션

문제풀이

• 완전탐색 + 시뮬레이션

문제코드

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;
import java.util.LinkedList;
import java.util.StringTokenizer;

public class Solution2383 {
    static class Comp implements Comparator<int[]>{
        @Override
        public int compare(int[] o1, int[] o2) {
            // TODO Auto-generated method stub
            return o1[2]-o2[2];
        }
    }
    public static Comp comp = new Comp();
    public static int Ans=Integer.MAX_VALUE;
    public static int Temp=0;
    public static int[][] map;
    public static int[][] stair;
    public static LinkedList<int[]> person;
    public static LinkedList<int[]> stair0;
    public static LinkedList<int[]> stair1;

    public static void Simulation() {
//        person_stair를 이용해서
//        stair0, stair1에 배정
        int psize;
        psize = person.size();
        int[] now_person;
        for (int i = 0; i < psize; i++) {
            now_person = person.get(i);
            if(person_stair[i]==0) {
                stair0.add(new int[] {    now_person[0],
                                        now_person[1],
                                        len(now_person[0], now_person[1], stair[0][0], stair[0][1])});
            }
            else {
                stair1.add(new int[] {    now_person[0],
                                        now_person[1],
                                        len(now_person[0], now_person[1], stair[1][0], stair[1][1])});
            }
        }

//        길이(거리순서대로 정렬) 이걸 매 시뮬레이션마다 실행하지않고 전역변수로 설정하는 법?
        stair0.sort(comp);
        stair1.sort(comp);



//        시간 진행해가면서 q에있는애들 터트리기
        int stair0_cnt=0;    //0번계단에 있는 사람 수
        int stair1_cnt=0;    //0번계단에 있는 사람 수
        Temp=0;
        while(true) {
            Temp++;
//            거리 1씩 줄여주고 , 0인경우(대기중이면 안내려가고, 내려가는중이면 내려줌)
//            계단0
            for (int i = 0; i < stair0.size(); i++) {
                if(stair0.get(i)[2]==0) {
//                    계단이 비었으면 내려가고
                    if(stair0_cnt < 3) {
                        stair0_cnt++;
                        stair0.get(i)[2]--;
                    }
//                    차있으면 대기
                    else {

                    }
                }
//                내려가고있거나, 계단에 다가오는경우
                else {
//                    계단 다 내려온 경우
                    if(stair0.get(i)[2]==-map[stair[0][0]][stair[0][1]]) {
                        stair0_cnt--;
                    }
                    stair0.get(i)[2]--;
                }
            }
//            계단1
            for (int i = 0; i < stair1.size(); i++) {
                if(stair1.get(i)[2]==0) {
//                    계단이 비었으면 내려가고
                    if(stair1_cnt < 3) {
                        stair1_cnt++;
                        stair1.get(i)[2]--;
                    }
//                    차있으면 대기
                    else {

                    }
                }
//                내려가고있거나, 계단에 다가오는경우
                else {
//                    계단 다 내려온 경우
                    if(stair1.get(i)[2]==-map[stair[1][0]][stair[1][1]]) {
                        stair1_cnt--;
                    }
                    stair1.get(i)[2]--;
                }
            }
//            계단 다 내려가면 remove(안해도될듯 stair_cnt 사용하기때문)


//            마지막 순서의 사람이 계단을 다 내려왔음.
            if((stair0.isEmpty() || stair0.get(stair0.size()-1)[2]<-map[stair[0][0]][stair[0][1]]) &&
               (stair1.isEmpty() || stair1.get(stair1.size()-1)[2]<-map[stair[1][0]][stair[1][1]])) {
//                정답 갱신
                if(Ans>Temp) {;
                    int debug=0;
                }
                Ans= Math.min(Ans, Temp);
//                초기화
                stair0.clear();
                stair1.clear();
                break;
            }
        }
    }

    public static int[] person_stair;
    public static int psize;
    public static void Subset(int cnt) {
        if(cnt==psize) {
//            System.out.println(Arrays.toString(person_stair));
            Simulation();
            return;
        }
        for (int i = 0; i < 2; i++) {
            person_stair[cnt]=i;
            Subset(cnt+1);
        }
    }

    public static int len(int pr, int pc , int sr, int sc) {
        return Math.abs(pr-sr)+Math.abs(pc-sc);
    }


    public static void main(String args[]) throws Exception
    {
        System.setIn(new FileInputStream("res/swea/2383.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        int T=Integer.parseInt(br.readLine());

        for(int test_case = 1; test_case <= T; test_case++)
        {
            int N=Integer.parseInt(br.readLine());
            map = new int [N][N];
            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());
                }
            }

            person = new LinkedList<>();
            stair0 = new LinkedList<>();
            stair1 = new LinkedList<>();

            stair = new int[2][2];
//            stair
            int scnt=0;
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    if(map[i][j]>=2) {
                        stair[scnt][0] = i;
                        stair[scnt][1] = j;
                        scnt++;
                    }
                }
            }

//            person
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    if(map[i][j]==1) {
                        person.add(new int[] {    i,
                                                j});
                    }
                }
            }
            psize = person.size();
            person_stair = new int[psize];
            Subset(0);

            System.out.println("#"+test_case+" "+Ans);
//            초기화
            Ans=Integer.MAX_VALUE;
        }
    }
}

아쉬운점

• 문제 제대로 안읽음 - 계단에 최대 3명까지임
• 인덱싱 실수함
  • 1번계단과 거리 구해야하는데 0번계단과 거리 구하는거 복붙한거 그대로 둠.

잘한점

• O(N) 계산
  • N=10 인거보고 2^10이라 완전탐색함
• Comparator 공부해서 매번 Nested method로 만들지 않고 아예 객체를 생성해서 호출시킴
  • 이렇게 안하면 Nested method 1024*2번 만듦 런타임 에러 걸릴 수도 있음

  • static class Comp implements Comparator<int[]>{
    @Override
    public int compare(int[] o1, int[] o2) {
        // TODO Auto-generated method stub
        return o1[2]-o2[2];
    }
    }
    public static Comp comp = new Comp();

  • stair0.sort(comp);
    stair1.sort(comp);