[삼성 SW Expert Academy] 점심 식사시간 2383 [Java]

| Problem

※ SW Expert Academy는 문제의 무단 복제를 금지하고 있기 때문에, 기재하지 못한 점 양해 부탁드립니다.

---

| Link

※ 하단의 Link를 클릭해도, 로그인 후 열람이 가능합니다.

swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5-BEE6AK0DFAVl&categoryId=AV5-BEE6AK0DFAVl&categoryType=CODE

SW Expert Academy

---

| 풀이

1. 최대 10명의 사람이 최대 2 종류의 계단으로 이동할 경우, 최소 시간을 출력해야 한다.
2. 따라서, 10명의 사람이 각각 계단으로 이동할 모든 경우의 수를 조사해야한다. ( dfs 또는 중복 순열)
3. 각 계단으로 이동시키며 해당 경우의 수 에서 모든 사람들이 계단을 내려가는 시간 구하기 ( Simulation )

• 계단 내려가는 것과 사람들이 계단으로 이동하는 작업은 동시에 일어나므로 
• while 조건 문 내에서
• 1. 계단 내려가기 ( 탈출 ) == 1s                                        //  [ qs 돌면서 ] 
• 2. 모든 탈출 조건 성공 시 return                                      // 모든 탈출인원 & 2개 계단 빌 때 까지 
• 3. 각 사람들을 계단으로 이동하기 == 1s                            // [ person 리스트 돌면서 ] 
• 순서를 따라야 한다.

 

• ex. 다른 순서대로 하게 된다면 ? 
• 1. 각 사람들을 계단으로 이동시키기 - 1s
• 2. 계단 내려가기 - 2s
• 3. 모든 탈출 조건 성공 시 return ==> 동시 작업이 아닌 조건이 된다.

---

| 어려웠던 점

 1) 중복순열 구하는 것까진 했는데 시뮬레이션에서 어떻게 처리해야 할지 어려웠다.

• 우선순위 queue인 P에 모두 넣어 놓고 가까운 순서대로 계단으로 보내고
• 그 중에서 0번 계단, 1번 계단으로 조건을 나누어 어렵게 처리하려고 했으나, 실패 ! 

2) 다른 사람들의 코드를 참조하며, 배열은 실제 메모리 주소를 참조한다..!

• 반복문에서 나온 q에 add를 해주는게 무슨 의미가 있는지 궁금했다.
• int 처럼, 일회성 q에 추가해주는 건 줄 알았다.
• 하지만, qs에서 나온 q는 같은 메모리 주소를 참조하기 때문에 실제 값을 꺼내고 다시 넣는 작업이라는 것!

---

| 코드

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

public class 점심식사시간_모의sw역테 {

	static int Tc, N; 
	static ArrayList<Person> person;
	static ArrayList<Stairs> stair;
	static int answer;
	static boolean[] visited;
	static int[][] map;
	
	private static class Person{
		int r;
		int c;
		int sel; // 1번 계단 or 2번 계단 
		int StairTime; // 실제 도착한 시간 
		int ArriveTime; // 계단 앞까지 도착시간 - 절대적인 거리
		Person( int r, int c){
			this.r = r;
			this.c = c;
		}
		@Override
		public String toString() {
			return "Person [r=" + r + ", c=" + c + ", sel=" + sel + ", StairTime=" + StairTime + ", ArriveTime="
					+ ArriveTime + "]";
		}
	}
	private static class Stairs{
		int r;
		int c;
		int height;
		Stairs( int r, int c, int height){
			this.r= r;
			this.c =c;
			this.height = height;
		}
		
	}
	
	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st ;
		
		st = new StringTokenizer(br.readLine()," ");
		Tc = Integer.parseInt(st.nextToken());
		
		for( int tc= 1; tc<=Tc; tc++) {
			st = new StringTokenizer(br.readLine()," ");
			N = Integer.parseInt(st.nextToken()); // 방의 크기 
			
			map = new int[N][N];
			person = new ArrayList<>(); // 사람의 수 
			stair = new ArrayList<>(); // 계단 총 2개 각각 위치
			answer = Integer.MAX_VALUE; // 답
			
			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 ) {
						person.add(new Person(i,j));
					} else if ( map[i][j] >= 2 ) {
						stair.add(new Stairs(i,j,map[i][j]));
					} else continue;
				}
			} // input
			
			// step1. 사람을 기준으로 어느 계단 선택할지 - 부분집합 
			sol(0);
			
			System.out.println("#"+tc+" "+answer );
		}
		
	}
	private static void print() {
		
		for( Queue<Person> person : qs ) {
			System.out.println(person.toString());
		}
	}
	
	static Queue<Person>[] qs = new LinkedList[2];
	private static int simulation() {
		PriorityQueue<Person> P = new PriorityQueue<>(); // 계단으로 부터 가장 거리가 짧은 순서대로 정렬하기
		qs[0] = new LinkedList<>(); // 1번 계단
		qs[1] = new LinkedList<>(); // 2번 계단
		int Person_arrive =0; // 계단 모두 내려간 사람의 수 
		int time = 1; // 시간
		
		while ( true ) {
			
			// 계단에 있으면 모두 내려보내기
			// step2. 다 정해지면, 각 정해진 계단으로 이동 후 - 계단 내려가기
			for( Queue<Person> q : qs ) { // qs : 계단 2개
				int size = q.size();
				
				if ( size == 0 ) continue;
				// 계단에 있는 모든 사람들 돌면서 이 계단은 1번, 2번 계단 모두 포함
				for( int i=0; i<size; i++) {
					Person p = q.poll();
					Stairs ps = stair.get( p.sel ); // 해당 사람의 계단 
					
					if ( p.StairTime + ps.height <= time ) {
						Person_arrive ++;
						continue; // 도착시간 + 계단 내려간 시간이 현재 시간안에 수행가능하다면 탈출시키기. 
					}
					// 그렇지 않으면 다시 넣어주기
					q.add(p);
				}
			}
			// Q. 궁금한 점 : 97 line 의 q와 아래 qs가 연관될까?
			
			// 탈출 조건 
			if ( Person_arrive == person.size() && qs[0].isEmpty() && qs[1].isEmpty()) return time;
			
			// 사람 모두 돌면서 계단으로 이동시키자.
			// 최대 3명까지 계단 이용 가능한 조건 고려
			for( int i=0; i< person.size(); i++) {
				if ( visited[i]) continue;
				// 도착할 때 까지 걸리는 시간이, 흐른 시간안에 도착이 가능하고
				// 해당 계단에 2명 이하라면?
				Person p = person.get(i);
				if( p.ArriveTime + 1 <= time && qs[ p.sel ].size() <= 2 ) { // + 1 은 도착하고 계단 내려갈 때 한번 더 이동해야해
					p.StairTime = time; // 실제 계단 앞까지 도착시간 적어주고
					visited[i] = true;
					qs[ p.sel ].add(p); // 해당 계단에 넣어주자
				}
			}
			time ++;
		}
		
	}
	
	private static void sol(int idx) {
		
		if ( idx == person.size()) {
			// step2. 다 정해지면, 각 정해진 계단으로 이동 후 - 계단 내려가기
			for( int i=0; i<person.size(); i++) {
				// 배정된 계단으로 부터 거리 설정
				Person p = person.get(i);
				person.get(i).ArriveTime = Math.abs( stair.get(p.sel).r - p.r ) + Math.abs( stair.get(p.sel).c - p.c );
			}
			visited = new boolean[idx];
			int ans = simulation();
			answer = answer > ans ? ans : answer;
			return;
		}
		
		person.get(idx).sel = 0; // 처음 들어오는 계단 위치
		sol(idx+1);
		person.get(idx).sel = 1; // 두번 째 들어오는 계단 위치
		sol(idx+1);
	}
	
}

---

| 보완할 점

1. 다른 사람의 코드를 보면 이해 못하겠는 코드가 많다.
2. 문제를 명확히 이해하지못하고 다른 방식으로 풀 정도의 체력이 부족한 것 같다. 복습하고 또 공부~!

---