[Java] swea 2383 점심식사시간

[Java] swea 2383 점심식사시간

 

swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5-BEE6AK0DFAVl&categoryId=AV5-BEE6AK0DFAVl&categoryType=CODE&problemTitle=sw&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=2

SW Expert Academy

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;

public class 모의SW_2383_점심식사시간 {
	static class Pos {
		int x, y;
		public Pos() {}
		public Pos(int x, int y) {
			this.x = x;
			this.y = y;
		}
	}
	static class Person {
		int num, remainTime;
		public Person() {}
		public Person(int num, int remainTime) {
			this.num = num;
			this.remainTime = remainTime;
		}
	}
	static int N;
	static int[] stairLen = new int[2];
	static Pos[] stairs = new Pos[2];
	static List<Pos> people;
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int T = Integer.parseInt(br.readLine());
		for (int testcase = 1; testcase <= T; testcase++) {
			MIN = Integer.MAX_VALUE;
			people = new ArrayList<>();
			for (int i = 0; i < 2; i++) {
				stairs[i] = new Pos();
			}
			N = Integer.parseInt(br.readLine());
			
			int idx=  0;
			for (int i = 0; i < N; i++) {
				StringTokenizer st = new StringTokenizer(br.readLine());
				for (int j = 0; j < N; j++) {
					int num = Integer.parseInt(st.nextToken());
					if(num == 1) {
						people.add(new Pos(i, j));
					}
					else if(num >= 2) {
						stairLen[idx] = num;
						stairs[idx].x = i;
						stairs[idx++].y = j;
					}
				}
			}
			peopleStairNum = new int[people.size()];
			
			subset(0);
			
			System.out.println("#" + testcase + " " + MIN);
		}
	} //main
	
	private static int[] peopleStairNum;
	private static int MIN;
	private static void subset(int cnt) {
		if(cnt == people.size()) {
			int time = solve();
			if(MIN > time-1) MIN = time-1;
			return;
		}
		
		peopleStairNum[cnt] = 0;
		subset(cnt+1);
		peopleStairNum[cnt] = 1;
		subset(cnt+1);
	} // subset
	
	private static int solve() {
		Queue<Person> stair1 = new LinkedList<>();
		Queue<Person> stair2 = new LinkedList<>();
		Queue<Person> wait1 = new LinkedList<>();
		Queue<Person> wait2 = new LinkedList<>();
		
		int t = 0, cnt = 0;
		while(true) {
			if(cnt == people.size() && stair1.size() == 0 && stair2.size() == 0 && wait1.size() == 0 && wait2.size() == 0) break;
			
			int size = wait1.size();
			while(size > 0) {
				Person p = wait1.poll();
				p.remainTime--;
				wait1.add(p);
				size--;
			}
			size = wait2.size();
			while(size > 0) {
				Person p = wait2.poll();
				p.remainTime--;
				wait2.add(p);
				size--;
			}
			
			if(cnt < people.size()) {
				for (int i = 0; i < peopleStairNum.length; i++) {
					if(peopleStairNum[i] == 0) {
						if(t == Math.abs(people.get(i).x - stairs[0].x) + Math.abs(people.get(i).y - stairs[0].y)) {
							wait1.add(new Person(i, 1));
							cnt++;
						}
					}
					else if(peopleStairNum[i] == 1) {
						if(t == Math.abs(people.get(i).x - stairs[1].x) + Math.abs(people.get(i).y - stairs[1].y)) {
							wait2.add(new Person(i, 1));
							cnt++;
						}
					}
				}
			}
			
			size = stair1.size();
			while(size > 0) {
				Person p = stair1.poll();
				p.remainTime--;
				if(p.remainTime > 0) stair1.add(p); 
				size--;
			}
			size = wait1.size();
			while(size > 0) {
				if(stair1.size() == 3) break;
				if(wait1.peek().remainTime <= 0) {
					Person p = wait1.poll();
					stair1.add(new Person(p.num, stairLen[0]));
				}
				size--;
			}
			size = stair2.size();
			while(size > 0) {
				Person p = stair2.poll();
				p.remainTime--;
				if(p.remainTime > 0) stair2.add(p); 
				size--;
			}
			size = wait2.size();
			while(size > 0) {
				if(stair2.size() == 3) break;
				if(wait2.peek().remainTime <= 0) {
					Person p = wait2.poll();
					stair2.add(new Person(p.num, stairLen[1]));
				}
				size--;
			}
			
			t++;
		} // while
		
		return t;
	} //solve
}

 

우선 subset 재귀 돌려서 각 사람이 1번 계단 가는 경우 2번 계단 가는 경우 이런식으로 모든 경우 완탐한다.

 

배열 다 뽑히면 solve()로 몇 분걸리는 지 확인한다,

solve()에서는

계단1큐, 계단2큐, 계단1내려가려고기다리는큐, 계단2내려가려고기다리는큐  이렇게 4개의 큐가 있다.

 

대기큐1과 대기큐2에 각 사람 전부 1분씩 줄인다.

그다음 사람 배열을 돌면서

계단과 사람 거리를 구하여 해당 시간에 도착했으면 대기큐1 혹은 2에 넣는다.

 

그다음

계단1큐와 계단2큐에서 내려가는 시간 1씩 줄이고 아직 다 안내려갔다면 다시 큐에 넣는다.

그리고 계단 1큐와 계단2큐가 각 사이즈 3 미만이라면 대기큐1과 대기큐2에서 빼서 넣는다.

 

모든 사람이 다 큐를 거쳤고, 모든 큐의 사이즈가 0일 때 while 문을 끝내면 된다.