[SW Expert] [모의 SW 역량테스트] 2383번 점심 식사시간 (Java)

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

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5-BEE6AK0DFAVl

 

 

모의 SW 역량테스트 마지막 문제다.

정답률 50% 치고는 굉장히 어려웠다.

다시 한번 느끼지만... 정답률은 정말 숫자에 불과한 듯하다.

 

사람들의 위치와 계단의 위치, 길이가 주어지면 사람들이 모두 내려가는 데 걸리는 최소 시간을 구해야 한다.

문제를 딱 보자마자 이게 대체 무슨 소린가 싶었다.

문제는 이해됐지만 어떻게 구현해야 할지 감이 안 왔고, 코드를 작성하기까지 꽤 오랜 시간이 걸렸다.

 

우선 사람들과 계단 사이의 거리를 구해야 한다.

int[2][m] 배열을 선언하여 사람들과 계단 사이의 거리를 전부 구해준다.

그 후, 사람들이 어느 계단으로 내려가야 할지 정한다.

계단은 총 2개뿐이므로, 사람들이 1번 계단으로 내려갈지 2번 계단으로 내려갈지 선택을 해준다. (choice 함수)

사람이 최대 10명이므로 총 1024가지의 경우의 수가 나온다.

 

계단을 선택하면 이제 차례로 내려가야 한다.

사람들이 선택한 계단과의 거리를 배열(int[] dst)로 받는다. 

이제 시간을 count 하면서 dst의 각각의 값을 -1씩 해준다.

dst의 값이 0이 된다면 계단 앞에 도착했다는 것을 의미한다. 계단을 내려갈 때는 dst의 값이 음수가 된다.

기존에 계단을 내려가던 사람이 3명이라면 계단 앞에서 대기를 해야 한다.

 

여기서 한 가지 주의할 점이 있는데, 내려가던 사람이 빠짐과 동시에 새로운 사람이 내려갈 수 있다는 점이다.

따라서 내려가던 사람이 빠지고 나서 새로운 사람이 계단을 내려가야 한다.

그 외에 계단을 내려가는 것과 계단이 꽉 차 있는지에 대해서는 Stairs 클래스에서 함수를 작성해서 관리했다.

 

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main {
    private static int m, min; // m: 사람 수
    private static int[][] distance;
    private static Stairs[] stairs;
    private static boolean[] choice;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        int n, idx, input;
        ArrayList<Index> people = new ArrayList<>();

        int T = Integer.parseInt(br.readLine());

        for (int t = 1; t <= T; t++) {
            stairs = new Stairs[2]; // 초기화
            min = Integer.MAX_VALUE;
            idx = 0;
            people.clear();

            n = Integer.parseInt(br.readLine()); // 입력
            for (int i = 0; i < n; i++) {
                st = new StringTokenizer(br.readLine());
                for (int j = 0; j < n; j++) {
                    input = Integer.parseInt(st.nextToken());
                    if (input == 1)
                        people.add(new Index(i, j));
                    else if (input != 0)
                        stairs[idx++] = new Stairs(i, j, input);
                }
            }

            m = people.size();
            choice = new boolean[m];
            distance = new int[2][m];
            for (int i = 0; i < 2; i++) {
                for (int j = 0; j < m; j++) {
                    distance[i][j] = getDist(stairs[i].index, people.get(j));
                }
            }
            choice(0);
            System.out.println("#" + t + " " + min);
        }
    }

    private static void choice(int depth) {
        if (m == depth) {
            solution(getDistInfo());
            return;
        }
        choice[depth] = true;
        choice(depth + 1);
        choice[depth] = false;
        choice(depth + 1);
    }

    private static void solution(int[] dst) {
        boolean[] check = new boolean[m];
        int count = 0;
        stairs[0].reset();
        stairs[1].reset();
        ArrayList<Integer> wait = new ArrayList<>();

        while (++count < min) { // min보다 오래 걸리면 종료
            wait.clear();
            for (int i = 0; i < m; i++) {
                if (check[i]) continue; // 이미 다 내려간 사람
                int s = (choice[i]) ? 0 : 1; // 계단 종류

                if (dst[i] == 0) wait.add(i); // 0인 사람은 밑의 for문에서 처리
                else {
                    if (--dst[i] < (-1) * stairs[s].value) {
                        stairs[s].out(); // 이동 완료
                        check[i] = true;
                    }
                }
            }
            for (Integer i : wait) {
                int s = (choice[i]) ? 0 : 1;
                if (stairs[s].status) { // 내려갈 수 있으면 내려감
                    dst[i]--;
                    stairs[s].down();
                }
            }
            if (isFinish(check)) min = count; // 다 내려오면
        }
    }

    private static boolean isFinish(boolean[] check) {
        for (int i = 0; i < m; i++) {
            if (!check[i]) return false;
        }
        return true;
    }

    private static int[] getDistInfo() {
        int[] result = new int[m];
        for (int i = 0; i < m; i++) {
            result[i] = (choice[i]) ? distance[0][i] : distance[1][i];
        }
        return result;
    }

    private static int getDist(Index a, Index b) { // 사람과 계단 사이 거리 측정
        return Math.abs(a.x - b.x) + Math.abs(a.y - b.y);
    }
}

class Index {
    int x, y;

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

class Stairs {
    Index index;
    int value, count;
    boolean status;

    public Stairs(int x, int y, int value) {
        this.index = new Index(x, y);
        this.value = value;
        this.count = 0;
        this.status = true;
    }

    public void down() {
        if (++count == 3) this.status = false; // 꽉차면 false 처리
    }

    public void reset() {
        this.count = 0;
        this.status = true;
    }

    public void out() {
        count--;
        this.status = true;
    }
}