[SWEA] 2383. [모의 SW 역량테스트] 점심 식사시간 Java

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

SW Expert Academy

---

1. 문제요약

모든 사람들이 계단을 내려가 이동하는 최소 시간을 구하는 문제이다.계단까지 이동하는시간 + 계단을 타고 내려가는 시간 의 최소값을 구한다.제약사항으로는 초마다 계단에 3명이 있으면 1초 대기 후 이동해야 한다.계단은 총 2개이며, 계단을 타고 내려가는 시간은 계단의 길이와 동일하다.계단까지 이동하는 시간은 맨하탄공식을 이용

2. 풀이

부분집합을 사용하여 완전탐색으로 가능한 모든 조합을 계산했다.1. 부분집합으로 사람마다 사용할 계단을 선택한다.

2. 기저조건에서, 각 계단을 사용하는 사람들을 우선순위큐에 넣는다. 이 때, 거리가 짧은 순서로 정렬된다.
    1) 거리가 짧은 사람부터 큐에서 꺼내, 시작시간 ~ 도착시간 반복문을 돌려 대기순서를 고려하여 계산한다 

          시작시간 : 계단 이동시간(맨하탄거리 공식) + 1(도착 후 대기시간)  

          도착시간 : 타고 내려가는시간(계단의 길이)을 계산한다.

          대기 :  time[매 초] => 매 초에 계단에 있는 사람의 수를 저장, 3이면 도착시간+1 하고 다음초부터 계산(continue)

    2) 0번 계단과 1번계단의 end 중 큰 값이 최종시간이 된다.

3. 모든 조합의 최종시간 중 최소값을 찾기 위해 min을 갱신해준다.

3. 코드

import java.util.*;
import java.io.*;

public class SW_2383_점심식사시간 {

	static int N, perIdx, min;
	static int[][] map;
	static Stair[] stair;
	static Person[] per;
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = null;
		int T = Integer.parseInt(br.readLine());
		for (int tc = 1; tc <= T; tc++) {
			N = Integer.parseInt(br.readLine());
			
			map = new int[N][N];
			stair = new Stair[2];
			per = new Person[N*N];
			int idx = 0; //계단번호 0,1
			perIdx = 0;
			
			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) { //사람이면 좌표저장
						per[perIdx++] = new Person(i, j);
					}
					if (map[i][j] >= 2) { //계단길이
						stair[idx++] = new Stair(i, j,map[i][j] ); //i:계단y좌표,j:계단x좌표,len:계단길이
					}
				}
			}
			min = Integer.MAX_VALUE;
			subset(0);
			System.out.println("#"+tc+" "+min);
		}
	}

	static void subset(int cnt) {
		if (cnt == perIdx) { //각자 계단 선택 완료 => 이제 시간 최소값을 찾자
			int totalTime = 0;
			for (int i = 0; i < 2; i++) {
				//1. 우선순위 큐에 해당 계단인 사람들만 가까운 순으로 넣어줌
				PriorityQueue<Person> pq = new PriorityQueue<> ();
				int time[] = new int[100]; // 매 초마다 사람 수 저장
				
				for (int j = 0; j < perIdx; j++) {
					if (per[j].stair == i) {
						pq.add(per[j]); //저장하면 해당 계단과 거리가 짧은 사람 순으로 정렬됨
					}
				}

				//2. 가까운순서부터 계단타고 내려가는 시간 계산
				while (!pq.isEmpty()) {
					Person front = pq.poll();
					int start = front.moveTime; //계단까지 이동거리(=이동시간)
					int end = start+stair[i].len; //계단 다내려간 시간
					for (int j = start; j < end; j++) {
						if (time[j] == 3) {
							end++;
							continue;
						}
						time[j]++;
					}
					totalTime = Math.max(totalTime, end); //최종시간은 end의 마지막 값, 0계단 end와 1계단end 중 큰게 최종시간임
				}
			}
			min = Math.min(totalTime, min); //각 조합들의 걸린시간 중 최소시간을 찾음
			return;
		}
		
		//1번계단 선택
		per[cnt].stair=0;
		per[cnt].moveTime = 1 + Math.abs( per[cnt].y-stair[0].y ) + Math.abs( per[cnt].x-stair[0].x );
		subset(cnt+1);
		//2번계단 선택
		per[cnt].stair=1;
		per[cnt].moveTime = 1 + Math.abs( per[cnt].y-stair[1].y ) + Math.abs( per[cnt].x-stair[1].x );
		subset(cnt+1);
	}
	
	static class Person implements Comparable<Person>{
		int y, x, moveTime, stair; //dist:계단과의거리, t:선택한 계단
		public Person(int y, int x) { 
			this.y = y;
			this.x = x;
		}
		@Override
		public int compareTo(Person o) {
			return this.moveTime - o.moveTime; //d작은순으로 정렬
		}
	}
	static class Stair {
		int y, x, len;
		public Stair(int y, int x, int len) {
			this.y = y;
			this.x = x;
			this.len = len;
		}
	}
}