(JAVA) 2383. [모의 SW 역량테스트] 점심 식사시간

Standard

문제 링크: https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5-BEE6AK0DFAVl

단계별로 잘 나눠야 하는 문제였음.
– 계단입구는 2개로 보장되어 있고, 사람 수만 변동성이 있음. 최대 10명이 조건이라서 아예 사람 관련 배열은 크기를 10으로 사용
– 각 사람이 계단입구1로 가느냐 2로 가느냐이니까, 경우의 수는 2^사람수 임.
– 각 사람의 정보를 1분 단위로 업데이트하는 식으로 구현.
– 처음에는 상태 0 (계단 입구로 가는 중)에 계단 입구로 가는 시간이 입력되어 있음. 상태 0일 때는 1분씩 감소시키고, 0분이 되면 상태1 (계단 입구 도착)으로 업데이트.
– 상태 1 (계단 입구 도착)일 때는 해당하는 계단에 3명 미만으로 있을 경우만 진입 (상태 2로 업데이트하고, 계단에 있어야 하는 시간 입력) / 이외의 경우에는 계속 상태 1에 있음
– 상태 2 (계단으로 이동 중)의 경우에는 시간 정보를 1 감소하고, 0이 되면 상태 3 (완료)로 이동.
단, 사람의 정보를 순차적으로 업데이트하기 때문에, 계단에서 사람이 나오는 정보가 늦게 업데이트되서 실제로는 계단 진입이 가능한데 불가능한 경우로 처리될 수 있음. 이 경우를 대비해서, 두 번째 상태 체크 (상태1->상태2로 이동) 로직을 추가로 구현함.

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

public class Solution {
	public static final int manMax = 10;
	public static void main(String[] args) throws IOException {
		//System.setIn(new FileInputStream("./src/sample_input.txt"));
		
		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
		
		try {
			int numCases = Integer.parseInt(reader.readLine());
	
			for (int num = 0; num < numCases; num++) {
				writer.write("#" + String.valueOf(num + 1) + " ");
				
				int numN = Integer.parseInt(reader.readLine()); // 지도 크기 
				
				// 계단입구 정보 (X, Y, 시간)
				int stairCount = 0;
				int[] stairX = new int[2];
				int[] stairY = new int[2];
				int[] stairCost = new int[2];
				
				// 사람 정보 (X, Y, 목적지)
				int manCount = 0;
				int[] manX = new int[manMax];
				int[] manY = new int[manMax];
				int[] manDest = new int[manMax];				
				int[] manStatus = new int[manMax]; // 0: 계단 입구로 가는 중, 1: 입구 도착, 2: 계단으로 이동 중, 3: 완료 
				int[] manMin = new int[manMax];
				
				// 사람, 계단 정보 생성
				for (int i = 0; i < numN; i++) {
					String[] tmp = reader.readLine().split(" ");

					for (int j = 0; j < tmp.length; j++) {
						int nextInfo = Integer.parseInt(tmp[j]);
						
						if (nextInfo == 0)
							continue;
						else {
							if (nextInfo == 1) { // 사람
								manX[manCount] = j;
								manY[manCount] = i;
								manCount++;
							}
							else {				 // 계단입구
								stairX[stairCount] = j;
								stairY[stairCount] = i;
								stairCost[stairCount] = nextInfo;
								stairCount++;
							}
						}						
					}
				}

				// 각 사람이 계단입구 1이나 2로 가니까 2^사람수 - 1 개 만큼 경우의 수가 생김
				int allPossibility = (int) Math.pow(2, manCount) - 1;

				// 최소값을 저장해야 하므로 최초 값은 매우 큰 수로 넣음
				int answer = 10000;
				
				// 실제 소요 시간 계산
				for (int i = 0; i <= allPossibility; i++) {
					int tmp_ =  i;

					List<String> stairZero = new ArrayList<String>(); // 첫번째 계단을 향하는 사람들 
					List<String> stairOne = new ArrayList<String>();  // 두 번째 계단을 향하는 사람들 
										
					// 목적지 입력
					for (int j = 0; j < manCount; j++) {
						manStatus[j] = 0;
						manDest[j] = tmp_ & 0b1;
												
						// 계단입구까지 걸리는 시간 계산
						manMin[j] = Math.abs(stairX[manDest[j]] - manX[j]) + Math.abs(stairY[manDest[j]] - manY[j]);
						
						tmp_ = tmp_ >> 1;
					}

					// 시간 소요 체크
					int minute = 0;
					while(true) {
						// 모든 사람이 이미 도착한 경우 루프를 나가도록 함 
						boolean allDone = true;
						for (int j = 0; j < manCount; j++) {
							if (manStatus[j] != 3) {
								allDone = false;
								break;
							}
						}
						if (allDone == true)
							break;
						
						for (int j = 0; j < manCount; j++) {
							switch (manStatus[j]) {
							case 0: // 계단 입구로 가는 중 
								if (manMin[j] == 0) {
									manStatus[j] = 1; // 입구 도착으로 변경
								}
								else
									manMin[j]--; // 0 될 때까지 감소
								break;
							case 1: // 입구 도착
								// 계단에 3명 이하만 있게 함 (초과하면 계속 status 1에 머무름)
								switch (manDest[j]) {
								case 0:
									if (stairZero.size() < 3) {
										stairZero.add(String.valueOf(j));
										manStatus[j] = 2; // 계단으로 이동중
										manMin[j] = stairCost[0];
									}
									break;
								case 1:
									if (stairOne.size() < 3) {
										stairOne.add(String.valueOf(j));
										manStatus[j] = 2; // 계단으로 이동중
										manMin[j] = stairCost[1];
									}
									break;
								}
								break;
							case 2: // 계단으로 이동 중
								manMin[j]--;
								
								if (manMin[j] == 0) {
									switch (manDest[j]) {
									case 0:
										stairZero.remove(String.valueOf(j));
										break;
									case 1:
										stairOne.remove(String.valueOf(j));
										break;
									}
									
									manStatus[j] = 3; // 완료
								}
									
								break;
							case 3: // 완료 
								continue;
							}
						}
						
						// 입구에 있는 경우만 다시 한 번 계산 (이미 나간 사람이 있을 경우 다시 진입 가능하도록 함)
						for (int j = 0; j < manCount; j++) {
							switch (manStatus[j]) {
							case 1: // 입구 도착
								// 계단에 3명 이하만 있게 함 (초과하면 계속 status 1에 머무름)
								switch (manDest[j]) {
								case 0:
									if (stairZero.size() < 3) {
										stairZero.add(String.valueOf(j));
										manStatus[j] = 2; // 계단으로 이동중
										manMin[j] = stairCost[0];
									}
									break;
								case 1:
									if (stairOne.size() < 3) {
										stairOne.add(String.valueOf(j));
										manStatus[j] = 2; // 계단으로 이동중
										manMin[j] = stairCost[1];
									}
									break;
								}
								break;
							}
						}	
						
						minute++;						
					}
					
					if (minute < answer)
						answer = minute;
				}
				
				writer.write(answer + System.lineSeparator());
				writer.flush();
			}
		} catch (IOException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
	}
}

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.