이번 문제는 해결법을 생각해내지 못했다.
머리속에 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
'PS > BOJ' 카테고리의 다른 글
| 4014 활주로 탐색 (0) | 2022.05.15 |
|---|---|
| 4013 특이한 자석 (0) | 2022.05.15 |
| 2382 미생물 격리 (0) | 2022.05.14 |
| 2117 홈 방범 서비스 (0) | 2022.05.14 |
| 2112 보호필름 (0) | 2022.05.14 |
