[알고리즘] 점심 식사시간

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5-BEE6AK0DFAVl

SW Expert Academy

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초를 기다리게 하여 논리가 맞지 않았었다.