모의 SW 역량테스트(점심 식사 시간)

[점심 식사 시간]

 

* 로직

• 계단 1과 2로 갈 수 있는 사람들의 모든 경우의 수를 구한다
• 각 경우의 수가 구해질 때마다 로직을 진행한다
• 계단 1과 2를 목적지로 하는 사람들에 대해 -> 도착하는데 걸리는 시간을 갱신한다(limit)
• 시간을 1분씩 늘려나가면서
  • 계단 1을 내려가고 있는 사람이 존재한다면(큐)
    • 각각 1분씩 늘려주고, 만약 다 내려갔다면 pop & cnt++를 해준다
  • 계단 1을 목적지로 하는 사람들의 시간을 1분씩 늘려주고
    • 만약 계단에 도착했다면
      • 이미 계단 1에 3명이 꽉찼다면 -> 1분 감소시키고, wait 표기를 해준다
      • 공간에 여유가 있다면 -> 계단 1 큐에 넣어준다
        (대기를 하는 사람의 경우 계단 1의 큐가 빈 경우 바로 내려갈 수 있기 때문에 wait 표기가 있다면 바로 진입하게끔 하기 위해 time=1로, 없다면 0으로 처리한다)
      • 큐에 넣어준 사람의 정보는 기존 리스트에서 제거해준다
    • 도착하지 못했다면
      • 시간만 1분씩 늘려준다
        
        
  • 위와 같은 과정을 계단 2에서도 반복한다
• 모든 사람이 계단을 다 내려갔다면 해당 경우의 수에 대한 로직을 종료하고, 그 다음 경우의 수를 고려한다

 

//점심 식사 시간
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

class PersonInfo implements Comparable<PersonInfo>{
	public int y, x;
	public int time;
	public int limit;
	public boolean wait;	//대기 표시

	public PersonInfo(int y, int x, int time, int limit) {
		super();
		this.y = y;
		this.x = x;
		this.time = time;
		this.limit = limit;
	}

	@Override
	public int compareTo(PersonInfo o) {
		return this.limit - o.limit;
	}
}

public class Solution {

	static int N;
	static int[][] Map;
	static ArrayList<PersonInfo> Person_list;
	static ArrayList<PersonInfo> Step_List;

	static boolean[] checked;
	static int Full = 3;
	
	static int cnt;
	static int answer;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;

		int testCase = Integer.parseInt(br.readLine());
		int t = 1;
		while (t <= testCase) {
			String input = br.readLine();
			N = Integer.parseInt(input);
			Map = new int[N][N];

			// input map, 사람 정보 리스트에 담기
			Person_list = new ArrayList<>();
			Step_List = new ArrayList<>();
			for (int i = 0; i < N; ++i) {
				input = br.readLine();
				st = new StringTokenizer(input, " ");
				for (int j = 0; j < N; ++j) {
					Map[i][j] = Integer.parseInt(st.nextToken());

					if (Map[i][j] == 1) {
						Person_list.add(new PersonInfo(i, j, 0, 0));
					}
					else if(Map[i][j] > 1) {
						Step_List.add(new PersonInfo(i, j, Map[i][j], 0));
					}
				}
			}

			// 가까운 계단의 큐로 사람의 정보 삽입
			answer = Integer.MAX_VALUE;
			doSolution();

			System.out.println("#" + t + " " + answer);
			t++;
		}
	}

	private static void doSolution() {
		// 1번, 2번계단에 진입하는 사람의 경우의 수 고려(조합)
		int index = 0;
		checked = new boolean[Person_list.size()];
		int limit = Person_list.size();
		doProcess(index, limit);

	}

	private static void doProcess(int index, int limit) {
		if (index >= limit) {
			// 계단 1과 계단 2에 대한 사람 구분
			doStart();
			return;
		}

		checked[index] = true;
		doProcess(index+1, limit);
		
		checked[index] = false;
		doProcess(index+1, limit);
	}

	private static void doStart() {
		ArrayList<PersonInfo> person_step1 = new ArrayList<>();
		ArrayList<PersonInfo> person_step2 = new ArrayList<>();
		for (int i = 0; i < Person_list.size(); ++i) {
			if (checked[i]) {
				person_step1.add(Person_list.get(i));
			} else {
				person_step2.add(Person_list.get(i));
			}
		}

		//각 계단별로 사람간의 거리 구해놓기
		PersonInfo step1 = Step_List.get(0);
		for(PersonInfo person : person_step1) {
			int distance = Math.abs(person.y - step1.y) + Math.abs(person.x - step1.x);
			person.time = 0;
			person.limit = distance;
		}
		
		PersonInfo step2 = Step_List.get(1);
		for(PersonInfo person : person_step2) {
			int distance = Math.abs(person.y - step2.y) + Math.abs(person.x - step2.x);
			person.time = 0;
			person.limit = distance;
		}
		
		//0분부터 1분씩 증가시켜 시뮬레이션
		int value = doSimulation(person_step1, person_step2);
		answer = Math.min(answer, value);
	}

	private static int doSimulation(ArrayList<PersonInfo> person_step1, ArrayList<PersonInfo> person_step2) {
		Queue<PersonInfo> queue_step1 = new LinkedList<>();
		Queue<PersonInfo> queue_step2 = new LinkedList<>();
				
		cnt=0;
		int size = person_step1.size() + person_step2.size();
		int time = 0;
		while(true) {			
//			if(person_step1.size() == 0 && person_step2.size()==0 
//					&& queue_step1.isEmpty() && queue_step2.isEmpty()) break;			
			
			if(cnt == size) break;
			time++;
			
			//계단1
			int type=0;
			doCalculate(person_step1, queue_step1, type);
			
			//계단2
			type=1;
			doCalculate(person_step2, queue_step2, type);						
		}	
		
		return time;
	}

	private static void doCalculate(ArrayList<PersonInfo> person_step, Queue<PersonInfo> queue_step, int type) {
		Collections.sort(person_step);
		
		//대기열에 사람이 존재한다면 -> 계단을 다 내려갔다면 -> pop
		if(queue_step.size() > 0) {			
			
			int size = queue_step.size();
			for(int s=0; s<size; ++s) {
				PersonInfo q = queue_step.poll();
				
				q.time++;
				if(q.time < q.limit) {
					queue_step.offer(q);
				}
				
				else cnt++;
			}
		}
				
		
		ArrayList<PersonInfo> removeIdxList = new ArrayList<>();
		for(int i=0; i<person_step.size(); ++i) {
			PersonInfo person = person_step.get(i);
			person.time++;
			
			//계단에 도달했다면 			
			if(person.time == person.limit) {
				
				//대기큐의 사이즈가 3개로 가득 찼는지 여부 판단
				//가능하다면 -> 계단을 내려가기까지의 시간 갱신
				if(queue_step.size() < Full) {
					
					//대기하고 있었다면 -> 바로 계단 내려가도록 하기
					if(person.wait) {
						person.limit = (Step_List.get(type).time+1);
						person.time = 1;
					}
					
					else {
						person.limit = (Step_List.get(type).time+1);
						person.time = 0;
					}
					
					person.wait = false;
					queue_step.offer(person);					
					removeIdxList.add(person);
				}
				
				else {
					person.wait = true;
					person.time--;
				}
			}
		}
		
		//제거 가능한 인덱스 제거
		for(PersonInfo removePerson : removeIdxList)
			person_step.remove(removePerson);
				
	}
}