[SWEA] 2383 - 점심 식사시간 자바

문제

N*N 크기의 정사각형 모양의 방에 사람들이 앉아 있다.
점심을 먹기 위해 아래 층으로 내려가야 하는데, 밥을 빨리 먹기 위해 최대한 빠른 시간 내에 내려가야 한다.
방 안의 사람들은 P로, 계단 입구를 S라고 했을 때 [Fig. 1]은 사람의 위치와 계단 입구의 위치를 표시한 모습이다.

[Fig. 1]

이동 완료 시간은 모든 사람들이 계단을 내려가 아래 층으로 이동을 완료한 시간이다.
사람들이 아래층으로 이동하는 시간은 계단 입구까지 이동 시간과 계단을 내려가는 시간이 포함된다.
    ① 계단 입구까지 이동 시간
        - 사람이 현재 위치에서 계단의 입구까지 이동하는데 걸리는 시간으로 다음과 같이 계산한다.
        - 이동 시간(분) = | PR - SR | + | PC - SC |
          (PR, PC : 사람 P의 세로위치, 가로위치, SR, SC : 계단 입구 S의 세로위치, 가로위치)    ② 계단을 내려가는 시간
        - 계단을 내려가는 시간은 계단 입구에 도착한 후부터 계단을 완전히 내려갈 때까지의 시간이다.
        - 계단 입구에 도착하면, 1분 후 아래칸으로 내려 갈 수 있다.
        - 계단 위에는 동시에 최대 3명까지만 올라가 있을 수 있다.
        - 이미 계단을 3명이 내려가고 있는 경우, 그 중 한 명이 계단을 완전히 내려갈 때까지 계단 입구에서 대기
        - 계단마다 길이 K가 주어지며, 계단에 올라간 후 완전히 내려가는데 K 분이 걸린다.
사람의 위치와 계단 입구의 위치 및 계단의 길이 정보가 표시된 N*N 크기의 지도가 주어진다.
이때, 모든 사람들이 계단을 내려가 이동이 완료되는 시간이 최소가 되는 경우를 찾고,
그 때의 소요시간을 출력하는 프로그램을 작성하라.


[예시]
방의 한 변의 길이 N 이 5인 지도가 [Fig. 2]와 같이 주어진 경우를 생각해보자.
지도 내에 1 은 사람을 나타내고, 2 이상 10 이하의 숫자는 계단의 입구를 나타내며 해당 숫자는 계단의 길이를 의미
[Fig. 2]에는 사람 6명이 있고, 계단은 2개가 있으며 길이는 각각 3과 5이다.

[Fig. 2]

다음은 이동 완료되는 시간이 최소가 되는 경우 중 하나이다.
    - 1번, 2번, 3번 사람은 길이가 3인 1번 계단을 통해 이동
    - 4번, 5번, 6번 사람은 길이가 5인 2번 계단을 통해 이동

이 경우, 모든 사람이 계단을 내려가 이동 완료하는 최소 시간은 9분이다.
다른 예시로, 한 변의 길이가 N인 방에 [Fig. 3]과 같이 배치되어 있는 경우를 생각해보자.
지도 내에 1 은 사람을 나타내고, 2 이상 10 이하의 숫자는 계단의 입구를 나타내며 해당 숫자는 계단의 길이를 의미

 

[Fig. 3]

다음은 이동이 완료되는 시간이 최소가 되는 경우 중 하나이다.
    - 1번, 2번, 3번, 4번 사람은 길이가 2인 1번 계단을 통해 이동
    - 5번, 6번 사람은 길이가 5인 2번 계단을 통해 이동

이 경우, 모든 사람이 계단을 내려가 이동 완료하는 최소 시간은 8분이다.

 

입력

입력의 맨 첫 줄에는 총 테스트 케이스의 개수 T가 주어지고, 그 다음 줄부터 T개의 테스트 케이스가 주어진다.
각 테스트 케이스의 첫 번째 줄에는 방의 한 변의 길이 N이 주어진다.
다음 N줄에는 N*N 크기의 지도의 정보가 주어진다.
지도에서 1은 사람을, 2 이상은 계단의 입구를 나타내며 그 값은 계단의 길이를 의미한다.

 

출력

테스트 케이스의 개수만큼 T줄에 T개의 테스트 케이스 각각에 대한 답을 출력한다.
각 줄은 "#x"로 시작하고 공백을 하나 둔 다음 정답을 출력한다. (x는 1부터 시작하는 테스트 케이스의 번호이다)
정답은 이동이 완료되는 최소의 시간을 출력한다.

 

제약사항

1. 시간제한 : 최대 50개 테스트 케이스를 모두 통과하는데, C/C++/Java 모두 3초
2. 방의 한 변의 길이 N은 4 이상 10 이하의 정수이다. (4 ≤ N ≤ 10)
3. 사람의 수는 1 이상 10 이하의 정수이다. (1 ≤ 사람의 수 ≤ 10)
4. 계단의 입구는 반드시 2개이며, 서로 위치가 겹치지 않는다.
5. 계단의 길이는 2 이상 10 이하의 정수이다. (2 ≤ 계단의 길이 ≤ 10)
6. 초기에 입력으로 주어지는 사람의 위치와 계단 입구의 위치는 서로 겹치지 않는다.

 

풀이 방법

1. 사람인 경우 people 리스트에, 계단인 경우 stairs 리스트에 각각의 좌표를 저장
2. 부분집합으로 people을 group1, group2로 나눔 (선택된 사람->group1, 선택되지 않은 사람-> group2)
3. group1, group2 리스트에 추가 할 때는 Person 클래스 이용(x좌표, y좌표, 계단과의 거리)
4. group1, group2 리스트는 계단과의 거리를 내림차순으로 정렬
   거리가 짧은 것 부터 계단에 도착하기 때문
5. 각각 그룹에서 걸리는 시간 계산
   - group에 사람이 3명 이하일 때 : 시간이 가장 오래 걸리는 사람
   - group에 사람이 3명보다 많을 때 : 자기보다 3개 앞에 있는 사람을 확인

     자기보다 3개 앞에 있는 사람이 아직 계단을 내려가는 중이라면 그 사람이 다 내려간 후 본인이 내려갈 수 있음

      자기보다 3개 앞에 있는 사람이 이미 계단을 다 내려갔다면 바로 내려갈 수 있음

6. group1에서 걸리는 시간과 group2에서 걸리는 시간 중 더 오래 걸리는 시간 리턴
7. 부분집합마다 계산 후 가장 짧게 걸리는 시간이 답!! 

 

내 코드

import java.awt.Point;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.StringTokenizer;

public class Solution_2383 {
	static int T, N, peopleCnt, minTime;
	static int[][] map;
	static boolean[] visited;
	static List<Point> stairs = new ArrayList<>();
	static List<Point> people = new ArrayList<>();
	
	static class Person implements Comparable<Person>{
		int x, y, dis;

		public Person(int x, int y, int dis) {
			super();
			this.x = x;
			this.y = y;
			this.dis = dis;
		}

		@Override
		public int compareTo(Person o) {
			return this.dis - o.dis;
		}

		@Override
		public String toString() {
			return "Person [x=" + x + ", y=" + y + ", dis=" + dis + "]";
		}
		
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		T = Integer.parseInt(br.readLine());
		for (int tc = 1; tc <= T; tc++) {
			N = Integer.parseInt(br.readLine());
			map = new int[N][N];
			stairs.clear();
			people.clear();
			
			for (int i = 0; i < N; i++) {
				StringTokenizer 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.add(new Point(j, i));
					else if(map[i][j] != 0) stairs.add(new Point(j, i));
				}
			}
			
			peopleCnt = people.size();
			visited = new boolean[peopleCnt];
			minTime = Integer.MAX_VALUE;
			choose(0);
			
			System.out.println("#" + tc + " " + minTime);
		}

		br.close();

	}
	
	static void choose(int n) {
		if(n == peopleCnt) {
			List<Person> group1 = new ArrayList<>();
			List<Person> group2 = new ArrayList<>();
			for (int i = 0; i < peopleCnt; i++) {
				int x = people.get(i).x;
				int y = people.get(i).y;
				int dis;
				if(visited[i]) {
					dis = Math.abs(x-stairs.get(0).x) + Math.abs(y-stairs.get(0).y);
					group1.add(new Person(x, y, dis));
				}
				else {
					dis = Math.abs(x-stairs.get(1).x) + Math.abs(y-stairs.get(1).y);
					group2.add(new Person(x, y, dis));
				}
			}
			
			Collections.sort(group1);
			Collections.sort(group2);
			
			minTime = Math.min(minTime, go(group1, group2));
			return;
		}
		
		visited[n] = true;
		choose(n+1);
		visited[n] = false;
		choose(n+1);
	}
	
	static int go(List<Person> group1, List<Person> group2) {
		return Math.max(calcTime(1, group1), calcTime(2, group2));
	}
	
	static int calcTime(int num, List<Person> group) {
		int time = 0;
		int stairTime = map[stairs.get(num-1).y][stairs.get(num-1).x];
		for (int i = 0; i < group.size(); i++) {
			if(i-3 < 0) {
				time = group.get(i).dis + 1 + stairTime;
			} else {
				if(group.get(i-3).dis + 1 + stairTime <= group.get(i).dis)
					time = group.get(i).dis + 1 + stairTime;
				else
					time = group.get(i-3).dis + 1 + stairTime + stairTime;
			}
		}
		
		return time;
	}
}