2383 점심 식사시간

 

이번 문제는 해결법을 생각해내지 못했다.

머리속에 Q를 사용하여 각 P를 처리해야될 것 같다까지는 떠올랐지만 실패했다.

이후 구현 방법에 대한 구체가 없어서 검색을 통해 아래의 해결 방법 및 코드를 학습했다.

 

전략

1. 계단이 총2개 존재하므로, 각 계단에 대해 Q를 할당한다.

2. P의 숫자나 맵의 크기가 시간초과가 발생할 정도로 크지 않기 때문에 완전탐색(DFS)을 통해 P가 계단을 선택하는 모든 경우의 수를 시뮬레이션한다. ( 이부분을 전혀 생각해내지 못함, 이 부분만 떠올랐으면 풀어 냈을지도 )

 

3. 각 case에 대한 simulation을 진행한다.

도착시간이 지나고 Q에 빈자리가 생기면 enqueue해준다. 

다음 iteration에서 , 계단을 내려가고 있는 P에 대한 처리를 진행한다. 

계단에 진입한 이후 k시간이 지나면 Q에서 제거, 그렇지 않다면 다시 enqueue해준다.

 

모든 P가 계단에 진입하고(cnt), q1/q2가 empty이면 모든 상황이 종료된다. 

 

유사한 문제가 나왔을 때 활용할 수 있도록 아래의 코드형태를 잘 기억하는게 좋을것 같다.

 

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;
import java.io.BufferedReader;
import java.io.File;
import java.io.FileOutputStream;
import java.io.InputStreamReader;
import java.io.PrintStream;

class P {
	int x, y;
	int arrivalTime;// 계단 도착시간
	int stair;// 계단 종류
	int stairTime;// 계단을 내려가기 시작한 시각

	P(int x, int y) {
		this.x = x;
		this.y = y;
	}

	public void setArrivalTime(S s) {
		arrivalTime = Math.abs(x - s.x) + Math.abs(y - s.y);
	}

}

class S {
	int x, y, k, cnt;

	S(int x, int y, int k) {
		this.x = x;
		this.y = y;
		this.k = k;
	}
}
class Solution {

	static int N;
	static int[][] map;
	static ArrayList<P> pList;
	static ArrayList<S> sList;
	static boolean[] visited;
	static Queue<P>[] Q;
	private static int ans;

	public static void main(String args[]) throws Exception {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int T;
		T = Integer.parseInt(br.readLine());

		StringTokenizer st = null;
		StringBuilder sb = new StringBuilder();
		long startTime = System.currentTimeMillis();
		for (int test_case = 1; test_case <= T; test_case++) {
			st = new StringTokenizer(br.readLine());
			N = Integer.parseInt(st.nextToken());
			pList = new ArrayList<>();
			sList = new ArrayList<>();
			for (int i = 0; i < N; i++) {
				st = new StringTokenizer(br.readLine());
				for (int j = 0; j < N; j++) {
					int v = Integer.parseInt(st.nextToken());
					if (v == 1) {
						pList.add(new P(i, j));
					} else if (v != 0) {
						sList.add(new S(i, j, v));
					}
				}
			}

			// init
			ans = Integer.MAX_VALUE;
			Q = new LinkedList[2];
			Q[0] = new LinkedList<>();
			Q[1] = new LinkedList<>();

			go(0);
			System.out.println("#" + test_case + " " + ans);
		}
	}

	private static void go(int level) {

		if (level == pList.size()) {
			visited = new boolean[pList.size()];
			int cur = simulation();
			ans = Math.min(cur, ans);
			return;
		}

		pList.get(level).stair = 0;
		pList.get(level).setArrivalTime(sList.get(0));
		go(level + 1);
		pList.get(level).stair = 1;
		pList.get(level).setArrivalTime(sList.get(1));
		go(level + 1);

	}

	private static int simulation() {
		int cnt = 0;
		int time = 0;

		while (true) {
			// Q안의 P중, 도착시간 + K가 현재시간과 같아지면, 제거한다.
			for (int i = 0; i < 2; i++) {
				int size = Q[i].size();

				for (int j = 0; j < size; j++) {
					P p = Q[i].poll();
					S s = sList.get(i);
					if (p.stairTime + s.k <= time)
						continue;

					Q[i].offer(p);
				}
			}

			if (cnt == pList.size() && Q[0].isEmpty() && Q[1].isEmpty()) {
				return time;
			}

			// Q안에 대기가 3개 미만이면 P를 넣어준다.
			for (int i = 0; i < pList.size(); i++) {
				P p = pList.get(i);
				Queue<P> q = Q[p.stair];
				if (visited[i])
					continue;

				if (p.arrivalTime + 1 <= time && q.size() < 3) {
					visited[i] = true;
					p.stairTime = time;
					q.offer(p);
					cnt++;
				}
			}
			time++;
		}
	}

}

 

 

참조 : https://velog.io/@hyeon930/SWEA-2383-%EC%A0%90%EC%8B%AC-%EC%8B%9D%EC%82%AC%EC%8B%9C%EA%B0%84-Java