[SWEA JAVA] 2383. [모의 SW 역량테스트] 점심 식사시간

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

SW Expert Academy

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.StringTokenizer;

public class Solution {
	public static int T, N, ans = 0, hNum;
	public static int[][] stairs;
	public static int[] arr;
	public static List<Hu> list;

	public static class Hu {
		int x, y, dis0, dis1, dist, end;

		public Hu(int x, int y, int dis0, int dis1, int dist, int end) {
			super();
			this.x = x;
			this.y = y;
			this.dis0 = dis0;
			this.dis1 = dis1;
			this.dist = dist;
			this.end = end;
		}

	}

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		T = Integer.parseInt(br.readLine());

		for (int tc = 1; tc <= T; tc++) {
			// 1. 입력받기
			N = Integer.parseInt(br.readLine());
			ans = 100;
			hNum = 0;
			// 1-1. map을 입력받으며 human과 stairs 위치 받기
			list = new ArrayList<>();
			stairs = new int[2][3];

			int cnt = 0;
			for (int i = 0; i < N; i++) {
				st = new StringTokenizer(br.readLine());
				for (int j = 0; j < N; j++) {
					int a = Integer.parseInt(st.nextToken());
					if (a == 1) {
						list.add(new Hu(i, j, 0, 0, 0, 0));
						hNum++;
					} else if (a > 1) {
						stairs[cnt][0] = i;
						stairs[cnt][1] = j;
						stairs[cnt++][2] = a;
					}
				}
			}

			for (int i = 0; i < list.size(); i++) {
				Hu cur = list.get(i);
				int ox = Math.abs(cur.x - stairs[0][0]);
				int oy = Math.abs(cur.y - stairs[0][1]);
				int tx = Math.abs(cur.x - stairs[1][0]);
				int ty = Math.abs(cur.y - stairs[1][1]);
				cur.dis0 = ox + oy; // 0번계단 까지의 길이
				cur.dis1 = tx + ty; // 1번계단 까지의 길이
			}

			// 2. 무슨 계단을 내려갈 것인지 부분집합 구해주기
			arr = new int[hNum];
			dfs(0);

			// 2-3. dp에서 가장 마지막에 나가는 값을 갱신 후 ans 와 비교 가장 작은 값 출력
			System.out.println("#" + tc + " " + ans);
		}

	}

	public static void dfs(int depth) {
		if (depth == hNum) {
			int min = 0;
			List<Hu> zero = new LinkedList<>();
			List<Hu> one = new LinkedList<>();

			for (int i = 0; i < hNum; i++) {
				Hu cur = list.get(i);
				// 거리 + 계단의 길이 구하기
				if (arr[i] == 0) {
					cur.dist = cur.dis0;
					cur.end = cur.dist + stairs[0][2] + 1;
					zero.add(cur);
				} else {
					cur.dist = cur.dis1;
					cur.end = cur.dist + stairs[1][2] + 1;
					one.add(cur);
				}
			}

			zero.sort((o1, o2) -> Integer.compare(o1.dist, o2.dist));
			one.sort((o1, o2) -> Integer.compare(o1.dist, o2.dist));
			int cnt0 = 0, cnt1 = 0;
			int[] ze, on;
			ze = new int[10];
			on = new int[10];
			for (Hu d : zero) {
				if (cnt0 < 3) {
					ze[cnt0++] = d.end;
				} else {
					if (ze[cnt0 - 3] > d.dist) {
						ze[cnt0] = ze[cnt0 - 3] + stairs[0][2];
					} else {
						ze[cnt0] = d.end;
					}
					cnt0++;
				}
			}

			for (Hu d : one) {
				if (cnt1 < 3) {
					on[cnt1++] = d.end;
				} else {
					if (on[cnt1 - 3] > d.dist) {
						on[cnt1] = on[cnt1 - 3] + stairs[1][2];
					} else {
						on[cnt1] = d.end;
					}
					cnt1++;
				}
			}

			if (zero.size() == 0) {
				cnt1--;
			} else if (one.size() == 0) {
				cnt0--;
			} else {
				cnt1--;
				cnt0--;
			}

			int z = ze[cnt0];
			int o = on[cnt1];

			min = Math.max(z, o);

			// 마지막 사람의 나가는 시간 계산
			if (ans > min) {
				ans = min;
			}

			return;
		}
		arr[depth] = 0; // 0번 계단 선택
		dfs(depth + 1);

		arr[depth] = 1; // 1번 계단 선택
		dfs(depth + 1);
	}

}