[swea] 2383번: 점심 식사시간 - java

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

SW Expert Academy

 

나의 코드

import java.awt.Point;
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Solution {
	static int n, map[][], person_cnt, stair_cnt, min_time;
	static ArrayList<Integer> people_stairs;
	static HashMap<Integer, Point> stairs; // 계단 번호, 계단 위치
	static HashMap<Integer, Point> people; // 사람 번호, 사람 위치

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringBuilder sb = new StringBuilder();
		StringTokenizer st;

		int T = Integer.parseInt(br.readLine());

		for (int t = 1; t <= T; t++) {
			n = Integer.parseInt(br.readLine());
			map = new int[n][n];
			stairs = new HashMap<>();
			people = new HashMap<>();
			people_stairs = new ArrayList<>();
			person_cnt = 0;
			stair_cnt = 0;
			for (int i = 0; i < n; i++) {
				st = new StringTokenizer(br.readLine());
				for (int j = 0; j < n; j++) {
					map[i][j] = Integer.parseInt(st.nextToken());
					if (map[i][j] == 1)
						people.put(person_cnt++, new Point(i, j)); // 사람 좌표 저장
					else if (map[i][j] > 1)
						stairs.put(stair_cnt++, new Point(i, j)); // 계단 좌표 저장
				}
			}
			for (int i = 0; i < person_cnt; i++)
				people_stairs.add(0);
			
			min_time = Integer.MAX_VALUE;
			dfs(0);
			sb.append("#").append(t).append(" ").append(min_time).append("\n");
		}
		bw.write(sb.toString());
		bw.flush();
		bw.close();
	}

	static void dfs(int cnt) {
		if (cnt == person_cnt) { // 모든 사람이 계단 선택 완료
			min_time = Math.min(min_time, Math.max(goDown(0), goDown(1)));
			return;
		}

		for (int i = 0; i < 2; i++) {
			people_stairs.set(cnt, i); // 0번계단 선택
			dfs(cnt + 1);
		}

	}

	static int goDown(int stair) {
		ArrayList<Integer> waiting = new ArrayList<>(); // 계단을 완전히 내려갈 때까지 남은 거리
		int time = 0;
		int total_people_cnt = 0; // 총 사람 수
		int complete_people_cnt = 0;
		int stair_length = map[stairs.get(stair).x][stairs.get(stair).y];

		for (int i = 0; i < person_cnt; i++) {
			if (people_stairs.get(i) == stair) {
				int dist = manHattanDistance(people.get(i).x, people.get(i).y, stairs.get(stair).x,
						stairs.get(stair).y);
				waiting.add(dist + stair_length); // 계단입구까지 거리 + 계단 길이
				total_people_cnt++;
			}
		}

		if (!waiting.isEmpty()) {

			Collections.sort(waiting); // 시간이 작게 걸리는 순으로 오름차순 정렬
			ArrayDeque<Integer> stairs = new ArrayDeque<>(); // 계단 큐

			while (complete_people_cnt < total_people_cnt) { // 아직 모든 사람이 계단을 다 내려가지 않았다면
				
				while (!stairs.isEmpty() && stairs.peekLast() <= 0) { // 도착한 사람
					stairs.pollLast();
					complete_people_cnt++;
				}

				while (stairs.size() < 3 && !waiting.isEmpty() && waiting.get(0) == stair_length) { // 계단에 올라간 사람이 3명
																									// 미만이라면
					stairs.addFirst(waiting.remove(0));
				}

				for (int i = 0; i < waiting.size(); i++) {
					if (waiting.get(i) != stair_length) // 계단입구가 아니라면 이동
						waiting.set(i, waiting.get(i) - 1);
				}

				int len = stairs.size();
				for (int i = 0; i < len; i++) {
					stairs.addLast(stairs.pollFirst() - 1);
				}

				time++;
			}
		}

		return time;

	}

	static int manHattanDistance(int x1, int y1, int x2, int y2) {
		return Math.abs(x1 - x2) + Math.abs(y1 - y2);
	}
}

 

정말 구현이 빡센 문제라고 생각한다...

위 문제를 풀기 위한 핵심적인 메서드를 2개 작성했다.

1. 각 사람이 계단을 선택

2. 선택한 계단에 따라 계단을 내려가는 시간 계산

 

 

먼저 계단을 선택하는 방법이다.

모든 사람이 하나의 계단을 이용하는 방법이 존재할 수도 있으므로 중복순열의 방법을 사용하였다.

만약, 모든 사람이 계단을 선택했다면, 선택한 계단을 내려가는데 걸리는 시간을 계산한다.

이때, 1번계단을 선택한 사람이 모두 내려가는데 걸린 시간 vs 2번계단을 선택한 사람이 모두 내려가는데 걸린 시간 중 더 오래 걸리는 시간이 최종적인 시간이 될 것이므로, 굳이 goDown() 메소드에서 두 개의 계단을 계산하지 않고, 각 계단을 나눠서 계단하도록 하였다.

 

 

다음으로는, 계단을 내려가는데 걸린 시간이다.

waiting 리스트에는 각 사람이 계단을 내려가는 것을 완료하기 까지 남은 거리를 저장하도록 하였다.

=> 각 사람의 남은 거리가 0이라면 계단을 끝까지 내려갔음을 의미한다.

즉, 사람~계단까지의 거리 + 계단길이가 저장되었다.

사람~계단까지의 거리는 맨해튼 거리로 계산하였다.

 

이제 시간을 계산할 차례이다.

먼저, waiting 의 거리를 오름차순으로 정렬하였으며, 계단에 올라와있는 사람을 관리하기 위한 Deque 을 만들었다.

 

 

반복문은 모든 사람이 계단을 내려갈 때까지 계속된다.

1. 계단 아래에 도착한 사람 

만약 stair 에 올라가있는 가장 밑에 있는 사람의 남은 거리가 0이라면, 해당 사람은 계단을 끝까지 내려간 것이므로 stairs 에서 제거해주고, 계단을 내려간 사람 변수를 1증가시킨다.

=> 계단의 한 층에 같은 사람이 2명 이상 존재할 수도 있으므로 남은 거리가 0인 사람을 모두 제거하기 위해 반복문으로 탐색하였다.

 

2. 계단 입성하기

만약 계단 deque 크기가 3 미만이라면, 사람이 계단에 더 올라올 수 있다.

이때, waiting 의 첫 번째 사람의 남은거리가 계단 길이 라면, 해당 사람은 계단 입구까지 도착한 것이므로, 계단에 올라올 수 있게 된다. 

따라서 waiting 에서 제거하여 계단 deque 의 앞에 추가한다.

 

3. 1초 증가

1초가 증가함에 따라, waiting중인 사람들과 stairs 에 입성한 사람들이 이동해야 한다.

waiting 하는 사람들 중, 아직 계단 입구에 오지 못한 사람이라면, 1초에 1씩 움직이므로 거리를 1감소시키고,

만약 이미 계단 입구인 사람이라면, 계단이 꽉차서 계단에 올라오지 못한 사람이르모 거리를 그대로 놔둔다.

 

또한, 계단에 있는 사람들도 한 칸씩 내려가야 하므로, 남은 거리를 1씩 감소시킨다.

이렇게 계단까지의 시간 계산이 끝났다.

 

즉, 한 번의 경우의 수에서 1번계단을 선택한 사람들이 계단을 모두 내려가는데 걸린 시간,

2번계단을 선택한 사람들이 계단을 모두 내려가는데 걸린 시간 중 큰 시간이 이번 경우의 수의 총 소요시간이 되겠다.

해당 소요시간을 min_time 과 비교하여, 더 작다면 min_time 을 갱신시킨다.

 

 

이렇게 구현이 복잡한 시뮬레이션 문제는 설계를 꼼꼼히 해야한다.

종이에 각 기능별 메소드를 세분화하여 잘 짜도록, 실수하지 않도록, 연습하는 것이 필요하다..!