[SWEA] 2383. 점심 식사시간 - Simulation

[SWEA] 2383. 점심 식사시간 - Simulation

제출일 : 2019-11-12

문제 풀이 시간 : 2D

난이도 : ★★★★★

Problem

link : https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5V61LqAf8DFAWu

Constraints

1. 시간제한 : 최대 50개 테스트 케이스를 모두 통과하는데, C/C++/Java 모두 3초
2. 방의 한 변의 길이 N은 4 이상 10 이하의 정수이다. (4 ≤ N ≤ 10)
3. 사람의 수는 1 이상 10 이하의 정수이다. (1 ≤ 사람의 수 ≤ 10)
4. 계단의 입구는 반드시 2개이며, 서로 위치가 겹치지 않는다.
5. 계단의 길이는 2 이상 10 이하의 정수이다. (2 ≤ 계단의 길이 ≤ 10)
6. 초기에 입력으로 주어지는 사람의 위치와 계단 입구의 위치는 서로 겹치지 않는다.

input

입력의 맨 첫 줄에는 총 테스트 케이스의 개수 T가 주어지고, 그 다음 줄부터 T개의 테스트 케이스가 주어진다.

각 테스트 케이스의 첫 번째 줄에는 방의 한 변의 길이 N이 주어진다.

다음 N줄에는 N*N 크기의 지도의 정보가 주어진다.

지도에서 1은 사람을, 2 이상은 계단의 입구를 나타내며 그 값은 계단의 길이를 의미한다.

Output

테스트 케이스의 개수만큼 T줄에 T개의 테스트 케이스 각각에 대한 답을 출력한다.

각 줄은 "#x"로 시작하고 공백을 하나 둔 다음 정답을 출력한다. (x는 1부터 시작하는 테스트 케이스의 번호이다)

Example

input

10
5
0 1 1 0 0
0 0 1 0 3
0 1 0 1 0
0 0 0 0 0
1 0 5 0 0
5
0 0 1 1 0
0 0 1 0 2
0 0 0 1 0
0 1 0 0 0
1 0 5 0 0
…

output

#1 9
#2 8
…

Solution & Inpression

모의 SW 역량테스트문제

1. 지도의 크기가 $N\times N$이고 사람, 계단의 길이가 주어진다.
   • 사람은 1 계단의 길이는 2 이상 10 이하
   • 계단의 개수는 2개이며 사람의 수는 최대 10명이다
2. 각 사람은 두 계단 중 한곳에 도착하여, 계단을 내려간다.
   • 계단을 완전이 내려가는 시간은 계단의 길이 K 만큼의 시간이 소요된다.
   • 계단은 최대 3명까지 동시에 이용이 가능
   • 계단에 도착하면 1분 후에 용이 가능

계단의 개수가 2개로 고정되기때문에 중복순열을 이용하여 각 사람이 이용할 수있는 모든 경우를 구한뒤

해당 경우의 시간을 구해 문제를 해결하였다.

지금까지 풀었던 문제중에 가장 어려웠던 문제였다.

Code

언어 : JAVA

메모리 : 36,012 kb

실행시간 : 177 ms

import java.io.FileInputStream;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Scanner;

class Point { // 방에서의 위치를 나타내는 클래스
    int r, c;

    public Point(int r, int c) {
        this.r = r;
        this.c = c;
    }
}

public class Solution {
    static int N, M, S;
    static int match[];

    static Point[] man;
    static Point[] stair;
    static int[] length;

    static int answer;

    public static void main(String[] args) throws Exception {
        System.setIn(new FileInputStream("res/input.txt"));
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        for (int tc = 1; tc <= T; tc++) {
            N = sc.nextInt();
            M = 0; // 사람 수
            S = -1; // 계단 수

            man = new Point[10]; // 최대 사람은 10명(위치 좌표를 저장)
            stair = new Point[2]; // 계단은 2개(위치 좌표를 저장)
            length = new int[2];// 계단의 길이 저장
            for (int i = 1; i <= N; i++) {
                for (int j = 1; j <= N; j++) {
                    int tmp = sc.nextInt();
                    if (tmp == 1)
                        man[M++] = new Point(i, j);
                    else if (tmp != 0) {
                        stair[++S] = new Point(i, j);
                        length[S] = tmp;
                    }
                }
            }

            answer = Integer.MAX_VALUE;
            match = new int[M];
            dfs(0); // 모든 경우의 수를 구한다.
            System.out.println("#" + tc + " " + answer);
        }
        sc.close();
    }

    // 중복순열: 모든 경우의 수를 구한다 최대 2^10
    private static void dfs(int depth) {
        if (depth == M) {
            solve();
            return;
        }
        for (int i = 0; i < 2; i++) {
            match[depth] = i;
            dfs(depth + 1);
        }
    }

    // 각사람이 어느 계단을 이용할 지 정해졌을 때에 필요한 시간을 계산하는 함수
    private static void solve() {
        PriorityQueue<Integer> pq0 = new PriorityQueue<>();
        PriorityQueue<Integer> pq1 = new PriorityQueue<>();

        for (int i = 0; i < M; i++) {
            if (match[i] == 0)
                pq0.add(dist(man[i], stair[0]));
            else
                pq1.add(dist(man[i], stair[1]));
        }

        int man = M; // 남은 이용자.
        int[] stair0 = new int[3]; // 계단을 이용하는 사람들의 남은 이용시간.
        int[] stair1 = new int[3];

        int time = 0;
        while (true) {

            // 종료 조건 : 계단을 모든 이용자가 이용할 때 까지.
            if (man == 0) {
                boolean flag = true;
                for (int i = 0; i < 3; i++) {
                    if (stair0[i] != 0) {
                        flag = false;
                        break;
                    }
                    if (stair1[i] != 0) {
                        flag = false;
                        break;
                    }
                }
                if (flag)
                    break;
            }

            for (int i = 0; i < 3; i++) { // 계단은 최대 3명까지 동시에 이용할 수 있다.
                if (stair0[i] == 0) { // 현재 이용하는 사람이 없을때
                    if (!pq0.isEmpty()) { // 이용할 사람이 있고(큐가 비어있지 않다면)
                        if (pq0.peek() <= time) { // 도착했다면
                            man--; // 남은 이용자수를 내린다.
                            stair0[i] = length[0];// 해당 계단의 이동시간을 주고
                            pq0.poll();
                        }
                    }
                } else { // 현재 계단을 사용하고 있다면
                    stair0[i]--; // 값을 내리고
                    if (stair0[i] == 0) {// 계단을 이용하고 있지 않다면.
                        if (!pq0.isEmpty()) {
                            if (pq0.peek() <= time) {
                                man--; // 이용자를 내린다.
                                stair0[i] = length[0];
                                pq0.poll();
                            }
                        }
                    }
                }

                if (stair1[i] == 0) { // 현재 이용하는 사람이 없을때
                    if (!pq1.isEmpty()) { // 이용할 사람이 있고(큐가 비어있지 않다면)
                        if (pq1.peek() <= time) { // 도착했다면
                            man--; // 남은 이용자수를 내린다.
                            stair1[i] = length[1];// 해당 계단의 이동시간을 주고
                            pq1.poll();
                        }
                    }
                } else { // 현재 계단을 사용하고 있다면
                    stair1[i]--; // 값을 내리고
                    if (stair1[i] == 0) {// 계단을 이용하고 있지 않다면.
                        if (!pq1.isEmpty()) {
                            if (pq1.peek() <= time) {
                                man--; // 이용자를 내린다.
                                stair1[i] = length[1];
                                pq1.poll();
                            }
                        }
                    }
                }

            } // end of for

            time++;
        } // end of while

        if (time < answer)
            answer = time;
    }

    private static int dist(Point man, Point stair) {
        return Math.abs(man.r - stair.r) + Math.abs(man.c - stair.c);
    }

}