[SWEA 2383] 점심 식사시간 (Java)

SWEA 2383 점심 식사시간

문제풀이

시뮬레이션 문제는 문제를 읽고서 설계를 잘 해야한다.

• 어떤 자료구조를 사용할지
• 어떤 순서로 진행될지

와 같은 부분들을 특히 모두 정해놓고 시작하지 않으면 후에 굉장한 시간낭비를 불러올 수 있다.

이 문제는 한 변의 길이가 최대 10이고 사람 수도 최대 10명 그리고 계단은 반드시 2 개 밖에 없기 때문에 완전탐색을 시도해볼 수 있다. 여기서 완전탐색은 각 사람마다 1계단과 2계단을 선택하는 경우를 모두 해보는 것이다.

• 존재하는 모든 사람들이 1계단 또는 2계단을 선택하였을 때 시뮬레이션을 진행하여 모두 이동하는데 걸리는 시간을 측정하고 반복하여 최솟값을 구한다.
• 계단에는 최대 3명까지만 올라갈 수 있으며 계단을 탈출한 것과 계단을 진입하는 것은 동시간에 일어날 수 있다. 따라서 구현상에서는 계단에서 탈출하는 동작을 먼저 수행하고 그 후에 계단에 진입하는 동작을 수행해야한다.

구현코드

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

public class Solution {
	
	static class Stair {
		int r, c, k;
		
		Stair(int r, int c, int k){
			this.r = r;
			this.c = c;
			this.k = k;
		}
	}
	
	static class Person {
		int r, c;
		int stair;
		int arriveTime;
		int stairTime;
		
		Person(int r, int c){
			this.r = r;
			this.c = c;
		}
		
		private void calArriveTime() {
			this.arriveTime = Math.abs(r - stairs[stair].r) + Math.abs(c - stairs[stair].c);
		}
	}
	
	static Queue<Person>[] qs;
	static ArrayList<Person> persons;
	static boolean[] visited;
	static Stair[] stairs;
	static int N, T, ans;
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = null;
		
		T = Integer.parseInt(br.readLine());
		
		for(int t = 1 ; t <= T ; ++t) {
			
			N = Integer.parseInt(br.readLine());
			
			persons = new ArrayList<>();
			qs = new LinkedList[2];
			qs[0] = new LinkedList<>();
			qs[1] = new LinkedList<>();
			stairs = new Stair[2];
			ans = Integer.MAX_VALUE;
			
			int stairIdx = 0;
			
			for(int r = 1 ; r <= N ; ++r) {
				st = new StringTokenizer(br.readLine());
				for(int c = 1 ; c <= N ; ++c) {
					int num = Integer.parseInt(st.nextToken()); 
					
					if(num == 0) {
						continue;
					}
					else if(num == 1) {
						persons.add(new Person(r, c));
					}
					else {
						stairs[stairIdx] = new Stair(r, c, num);
						stairIdx++;
					}
				}
			}
			
			
			go(0);
			
			System.out.println("#" + t + " " + ans);
		}
	}

	private static void go(int idx) {
		
		if(idx == persons.size()) {
			visited = new boolean[persons.size()];

			int cur = simulation();
			
			ans = ans > cur ? cur : ans;
			return;
		}
		
		// 첫번째 계단 이용하기 
		persons.get(idx).stair = 0;
		persons.get(idx).calArriveTime();
		go(idx + 1);
		
		// 두번째 계단 이용하기
		persons.get(idx).stair = 1;
		persons.get(idx).calArriveTime();
		go(idx + 1);
	}

	private static int simulation() {
		int cnt = 0;
		int time = 1;
		
		while(true) {
			// 내려가고
			for(Queue<Person> q : qs) {
				int size = q.size();
				
				for(int i = 0 ; i < size ; ++i) {
					Person p = q.poll();
					Stair s = stairs[p.stair];
					
					if(p.stairTime + s.k <= time) {
						continue;
					}
					
					q.offer(p);
				}
			}
			
			if(cnt == persons.size() && qs[0].isEmpty() && qs[1].isEmpty()) {
				return time;
			}
			
			// 큐에 넣고
			for(int i = 0 ; i < persons.size() ; ++i) {
				if(visited[i]) continue;
				
				Person p = persons.get(i);
				Queue<Person> q = qs[p.stair];
				
				if(p.arriveTime + 1 <= time && q.size() < 3) {
					p.stairTime = time;
					visited[i] = true;
					q.offer(p);
					cnt++;
				}
			}
			time++;
		}
	}
}