[알고리즘] 점심 식사시간
2024. 2. 25. 09:07ㆍ알고리즘 풀이/Java
https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5-BEE6AK0DFAVl
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;
public class Solution {
static int P;
static int[] comb;
static List<int[]> people;
static List<int[]> stairs;
static int minTime;
static StringBuilder sb = new StringBuilder();
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
int T = Integer.parseInt(br.readLine());
for (int testCase = 1; testCase <= T; testCase++) {
int N = Integer.parseInt(br.readLine());
people = new ArrayList<>();
stairs = new ArrayList<>();
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < N; j++) {
int cur = Integer.parseInt(st.nextToken());
if (cur == 1) {
people.add(new int[]{i, j});
} else if (cur > 1) {
stairs.add(new int[]{i, j, cur});
}
}
}
P = people.size();
comb = new int[P];
minTime = Integer.MAX_VALUE;
dfs(0);
sb.append("#").append(testCase).append(" ").append(minTime).append("\n");
}
System.out.println(sb);
}
private static void dfs(int depth) {
if (depth == P) {
simulation();
return;
}
comb[depth] = 0;
dfs(depth + 1);
comb[depth] = 1;
dfs(depth + 1);
}
private static void simulation() {
Queue<Integer>[] stairWaiting = new Queue[2];
stairWaiting[0] = new ArrayDeque<>();
stairWaiting[1] = new ArrayDeque<>();
Queue<Integer>[] stairExecuting = new Queue[2];
stairExecuting[0] = new ArrayDeque<>();
stairExecuting[1] = new ArrayDeque<>();
for (int i = 0; i < P; i++) {
int index = comb[i];
int sum = Math.abs(people.get(i)[0] - stairs.get(index)[0]) + Math.abs(
people.get(i)[1] - stairs.get(index)[1]);
stairWaiting[index].add(sum);
}
int time = 0;
while (true) {
int count = 0;
for (int i = 0; i < 2; i++) {
if (stairWaiting[i].isEmpty()) {
count++;
}
if (stairExecuting[i].isEmpty()) {
count++;
}
}
if (count == 4) {
break;
}
time++;
for (int i = 0; i < 2; i++) {
int size = stairExecuting[i].size();
for (int j = 0; j < size; j++) {
int wait = stairExecuting[i].poll();
if (wait - 1 != 0) {
stairExecuting[i].add(wait - 1);
}
}
size = stairWaiting[i].size();
for (int j = 0; j < size; j++) {
int wait = stairWaiting[i].poll();
if (wait == -1) {
if (stairExecuting[i].size() < 3) {
stairExecuting[i].add(stairs.get(i)[2]);
} else {
stairWaiting[i].offer(-1);
}
} else if (wait - 1 == 0) {
if (stairExecuting[i].size() < 3) {
stairExecuting[i].add(stairs.get(i)[2] + 1);
} else {
stairWaiting[i].offer(-1);
}
} else {
stairWaiting[i].offer(wait - 1);
}
}
}
}
minTime = Math.min(minTime, time);
}
}
나의 풀이
- 완전 탐색
- 시뮬레이션으로 구현
- 계단까지 가는 큐와 계단을 올라가는 큐로 나누어 구현
- for문의 사이즈를 특정 자료구조의 크기로 했는데 그 자료구조의 특정 원소를 for 문 안에서 삭제해야 할때 조심하자.
사이즈가 줄어들기 때문에 제대로된 결과가 나오지 않는다. 이것 때문에 논리는 거의 맞는데 많이 헤맸다.
- 계단에 도착하면 1초를 기다려야 한다. 그런데 1초 후에 계단을 못갈 수도 있다. 이 경우에는 계단을 오를 순번이 되었다면 1초를 기다리지 않고 바로 올라가야 한다. 이를 고려하지 않고 계단 오를 순번이 되었을때에도 1초를 기다리게 하여 논리가 맞지 않았었다.
'알고리즘 풀이 > Java' 카테고리의 다른 글
[알고리즘] 낚시왕 (1) | 2024.02.27 |
---|---|
[알고리즘][X] 공주님의 정원 (0) | 2024.02.26 |
[알고리즘] DP 테이블의 차원에 대한 꿀팁 (0) | 2024.02.24 |
[알고리즘] ⚾ (0) | 2024.02.23 |
[알고리즘] 게리맨더링 (0) | 2024.02.22 |