문제

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

코드 (Java)

import java.util.*;
import java.io.*;

class Solution
{
	
	private static int cnt;
	private static int[] selected;
	private static int[] combArrivalTime;
	private static int[] door1ArrivalTime, door2ArrivalTime;
	private static int waiting1 = 0, waiting2 = 0;
	private static ArrayList<Integer> stair1runners = new ArrayList<>(), stair2runners = new ArrayList<>();
	private static ArrayList<int[]> doorPos;
	
	public static class Node implements Comparable<Node> {
		int cost;
		int idx;
		
		@Override
		public int compareTo(Node o) {
			return Integer.compare(cost, o.cost);
		}
		
		public Node(int cost, int idx) {
			this.cost = cost;
			this.idx = idx;
		}
		
		
	}
	
	public static void main(String args[]) throws Exception
	{
//		System.setIn(new FileInputStream("res/input.txt"));

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		int T;
		T=Integer.parseInt(br.readLine().trim());

		for(int test_case = 1; test_case <= T; test_case++)
		{
			int N = Integer.parseInt(br.readLine().trim());
			ArrayList<int[]> personPos = new ArrayList<>();
			doorPos = new ArrayList<>();
			cnt = 0;
			
			for (int r = 0; r < N; ++r) {
				StringTokenizer st = new StringTokenizer(br.readLine().trim());
				for (int c = 0; c < N; ++c) {
					int p = Integer.parseInt(st.nextToken());
					if (p == 1) {
						personPos.add(new int[] {r, c});
						++cnt;
					} else if (p != 0) {
						doorPos.add(new int[] {r, c, p});
					}
				}
			}
			
			door1ArrivalTime = new int[cnt];
			door2ArrivalTime = new int[cnt];
			combArrivalTime = new int[cnt];
			
			for (int i = 0; i < cnt; ++i) {
				door1ArrivalTime[i] = Math.abs(doorPos.get(0)[0] - personPos.get(i)[0]) + Math.abs(doorPos.get(0)[1] - personPos.get(i)[1]);
				door2ArrivalTime[i] = Math.abs(doorPos.get(1)[0] - personPos.get(i)[0]) + Math.abs(doorPos.get(1)[1] - personPos.get(i)[1]);
			}
			
//			for (int i = 0; i < cnt; ++i) {
//				System.out.printf("%d %d\n", personPos.get(i)[0], personPos.get(i)[1]);
//			}
//			
//			for (int i = 0; i < 2; ++i) {
//				System.out.printf("%d %d\n", doorPos.get(i)[0], doorPos.get(i)[1]);
//			}
//			
//			for (int i = 0; i < cnt; ++i) {
//				System.out.printf("%d ", door1ArrivalTime[i]);
//			}
//			System.out.printf("\n");
//			for (int i = 0; i < cnt; ++i) {
//				System.out.printf("%d ", door2ArrivalTime[i]);
//			}
//			System.out.printf("\n");
//			System.out.printf("\n");
			
			selected = new int[cnt];
			bw.write("#" + test_case + " " + solve(0) + "\n");

		}
		br.close();
		bw.flush();
		bw.close();
	}
	
	private static int solve(int selecting) {
		int min = Integer.MAX_VALUE;
		if (selecting != cnt) {
			selected[selecting] = 0;
			combArrivalTime[selecting] = door1ArrivalTime[selecting];
			min = Math.min(min, solve(selecting+1));
			selected[selecting] = 1;
			combArrivalTime[selecting] = door2ArrivalTime[selecting];
			min = Math.min(min, solve(selecting+1));
		} else {
			//we now need to solve for this combination
			int time = 0;
			PriorityQueue<Node> pq = new PriorityQueue<>();
			for (int i = 0; i < cnt; ++i) {
				pq.add(new Node(combArrivalTime[i], i));
			}
			
			while (!pq.isEmpty() || waiting1 != 0 || waiting2 != 0 || !stair1runners.isEmpty() || !stair2runners.isEmpty()) {
				++time;
				//finished runners exit the stairs
				for (int i = stair1runners.size() - 1; i >= 0; --i) {
					stair1runners.set(i, stair1runners.get(i) + 1);
					if (stair1runners.get(i) >= doorPos.get(0)[2]) {
						stair1runners.remove(i);
					}
				}
				for (int i = stair2runners.size() - 1; i >= 0; --i) {
					stair2runners.set(i, stair2runners.get(i) + 1);
					if (stair2runners.get(i) >= doorPos.get(1)[2]) {
						stair2runners.remove(i);
					}
				}
				
				//ready pending runners enter the stairs
				while (stair1runners.size() < 3) {
					if (waiting1 == 0) break;
					stair1runners.add(0);
					waiting1--;
					
				}
				
				while (stair2runners.size() < 3) {
					if (waiting2 == 0) break;
					stair2runners.add(0);
					waiting2--;
				}
				
				while (!pq.isEmpty() && pq.peek().cost == time) {
					int pidx = pq.poll().idx;
					if (selected[pidx] == 0) {
						//needs to go to stair1.
						waiting1++;
					} else {
						waiting2++;
					}
				}
			}
			
//			System.out.println(time);
			
			min = time;
		}
		
		return min;
	}
}

풀이

• 고민하다 못풀었는데, 뭔가 간지나는 방법이 있나 싶었다가 확인해보니 그냥 노가다였다. (...)

• 자료구조를 좀 많이 사용했는데, 효율성을 중시한다면 몇개는 없앨 수 있긴...하지만 굳이싶다. 그러면 메모리 접근을 좀 자주해야 해서.

• 범위가 작으면 우선 브루트포스 형식으로 풀 수 있는지를 한번쯤 고민해보도록 하자는 교훈을 얻음.