[모의 SW 역량 테스트] 점심 식사 시간
1. 핵심 개념 및 근거
필요한 개념 및 자료구조
- 완전 탐색: 모든 사람이 두 개의 계단 중 하나를 선택하는 모든 경우의 수를 구합니다.
- 시뮬레이션: 각 계단별로 도착한 사람들을 시간 순서대로 처리하며, 계단 위 최대 3명 제한을 관리합니다.
- 정렬: 계단 입구에 도착하는 시간순으로 사람들을 정렬하여 먼저 도착한 사람이 먼저 내려가게 합니다.
선택 근거 및 제약사항
- 사람 수: 사람 수가 최대 10명으로 매우 적습니다. 각 사람이 계단 A 또는 B를 선택하는 경우의 수는 1024가지뿐입니다. 따라서 브루트 포스(완전 탐색)가 가능합니다.
- 계단 이용 제한: “계단 위에는 동시에 최대 3명까지만 있을 수 있다”는 조건 때문에 단순히 도착 시간만 계산해서는 안 되며, 대기 시간을 포함한 시뮬레이션이 필수적입니다.
시간 복잡도
- 계단 배정 (2^N) X 계단 시뮬레이션 (Nlog N 정렬 + 최대 시간 흐름)
2. 추론 과정
- “모든 사람이 이동을 완료하는 최소 시간”: 최적화 문제처럼 보이지만, 범위가 작으므로 모든 조합을 시도하는 BFS/DFS 혹은 완전 탐색을 떠올려야 합니다.
- “계단 입구까지의 거리”: 맨해튼 거리를 사용해 도착 시간을 미리 계산할 수 있음을 의미합니다.
- “최대 3명”: 이 조건이 핵심입니다. 먼저 온 사람이 먼저 내려가고, 꽉 찼으면 기다려야 하므로 Queue 자료구조가 적합함을 암시합니다.
3. 설계 및 접근
- 데이터 수집: 사람의 위치(
List<Person>)와 계단의 위치 및 길이(Stair[])를 저장합니다. - 계단 배정 (DFS): 0번 사람부터 N-1번 사람까지 계단 0을 갈지, 계단 1을 갈지 결정합니다.
- 시뮬레이션
- 선택된 계단별로 사람들의 도착 시간을 계산하고 오름차순 정렬합니다.
- 시간을 1씩 증가시키거나, 큐를 사용하여 계단에 진입한 사람의 ‘완료 예정 시간’을 관리합니다.
- 계단 진입 조건: (현재 시간 ≥ 도착 시간 + 1) AND (계단 이용자 < 3명).
- 최솟값 갱신: 모든 배정 케이스 중 가장 빨리 끝나는 시간을 정답으로 취합니다.
4. 예시 시뮬레이션
상황: 계단 길이 3, 도착 예정 시간 [1, 1, 1, 1]인 사람 4명.
| 시간 (Time) | 입구 대기 | 계단 내부 | 상황 설명 |
|---|---|---|---|
| T=1 | [1, 1, 1, 1] | [] | 4명 모두 도착. 하지만 1분 대기 규칙으로 아무도 못 들어감. |
| T=2 | [1] | [5, 5, 5] | 3명이 진입. 완료 시간은 2 + 3 = 5. 1명은 정원 초과로 대기. |
| T=3 | [1] | [5, 5, 5] | 변동 없음. |
| T=4 | [1] | [5, 5, 5] | 변동 없음. |
| T=5 | [] | [8] | [중요] 3명이 나감(T=5). 빈자리가 생겨 대기자 1명 진입. 완료 시간 5 + 3 = 8 |
| T=8 | [] | [] | 마지막 사람이 나감. 시뮬레이션 종료. |
5. 주의 사항
- 대기 시간 1분: 계단에 도착하자마자 내려가는 게 아니라, 도착 후 1분 뒤에 내려갈 수 있습니다.
- 공백 계단 처리: 특정 계단에 아무도 배정되지 않는 경우를 반드시 예외 처리해야 합니다.
- 동시 퇴출/진입: 특정 시간에 계단에서 사람이 나가는 것과 새로운 사람이 들어가는 것이 같은 시간에 일어날 수 있습니다. (나가는 처리를 먼저 해야 자리가 생깁니다.)
6. 코드 풀이
6.1 시간대별 로직
계단에서 나가는 사람 처리
while (!onStair.isEmpty() && onStair.peek() == time) {
onStair.poll();
finishedCount++;
}
- 계단에서 사람이 나가야 빈자리가 생겨 대기 중인 사람이 즉시 들어올 수 있기 때문입니다.
- 큐의 맨 앞사람의 완료 시간이 현재 시간과 같다면, 그 사람은 계단을 다 내려온 것이므로 제거합니다.
계단에 들어오는 사람 처리
while (!arrivalTimes.isEmpty() && arrivalTimes.peek() < time && onStair.size() < 3) {
arrivalTimes.poll();
onStair.add(time + stair.length);
}
- 조건 1 (
arrivalTimes.peek() < time): 문제에서 “도착 후 1분 뒤부터 진입 가능”이라고 했습니다. 즉, 도착 시간 D라면 D+1분부터 들어갈 수 있습니다. 따라서현재 시간(time) > 도착 시간이어야 합니다. - 조건 2 (
onStair.size() < 3): 계단에는 동시에 3명까지만 있을 수 있습니다 - 진입 시:
현재 시간 + 계단 길이를 큐에 넣습니다. 이것이 이 사람이 계단을 다 내려가게 될 미래의 시간입니다.
시간대별 로직 전체 코드
while (finishedCount < totalToProcess || !onStair.isEmpty()) {
time++;
// 1. 계단에서 나갈 사람 처리 (현재 시간이 완료 시간인 경우)
while (!onStair.isEmpty() && onStair.peek() == time) {
onStair.poll();
finishedCount++;
}
// 2. 계단에 들어올 사람 처리
while (!arrivalTimes.isEmpty() && arrivalTimes.peek() < time && onStair.size() < 3) {
arrivalTimes.poll();
onStair.add(time + stair.length); // 현재 시간 + 계단 길이 = 완료 시간
}
}
6.2 전체 코드
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.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;
public class Solution {
static int N, minTime;
static List<Person> persons;
static List<Stair> stairs;
static int[] selectedStair; // 각 사람이 선택한 계단 인덱스
public static void main(String[] args) throws NumberFormatException, IOException {
// TODO Auto-generated method stub
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
int T = Integer.parseInt(br.readLine());
// tc 수행
for (int tc = 1; tc <= T; tc++) {
// 방의 크기 입력
N = Integer.parseInt(br.readLine());
// 초기화
persons = new ArrayList<>();
stairs = new ArrayList<>();
minTime = Integer.MAX_VALUE;
// 지동 정보 입력
for (int i = 0; i < N; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
for (int j = 0; j < N; j++) {
int val = Integer.parseInt(st.nextToken());
if (val == 1)
persons.add(new Person(i, j));
else if (val > 1)
stairs.add(new Stair(i, j, val));
}
}
// 계단 선택 인덱스 초기화
selectedStair = new int[persons.size()];
// 처리
divide(0);
// 출력 내용 추가
sb.append("#" + tc + " " + minTime + "\n");
} // tc 종료
// 출력
System.out.println(sb);
}
static class Person {
int r, c, arrivalTime;
public Person(int r, int c) {
super();
this.r = r;
this.c = c;
}
}
static class Stair {
int r, c, length;
public Stair(int r, int c, int length) {
super();
this.r = r;
this.c = c;
this.length = length;
}
}
static void divide(int idx) {
if (idx == persons.size()) {
minTime = Math.min(minTime, simulate());
return;
}
selectedStair[idx] = 0;
divide(idx + 1);
selectedStair[idx] = 1;
divide(idx + 1);
}
static int simulate() {
int totalMax = 0;
// 두 개의 계단에 대해 각각 시뮬레이션
for (int s = 0; s < 2; s++) {
Stair stair = stairs.get(s);
PriorityQueue<Integer> arrivalTimes = new PriorityQueue<>();
// 해당 계단을 선택한 사람들의 도착 시간 계산
for (int i = 0; i < persons.size(); i++) {
if (selectedStair[i] == s) {
int dist = Math.abs(persons.get(i).r - stair.r) + Math.abs(persons.get(i).c - stair.c);
arrivalTimes.add(dist);
}
}
// 계단 이용 시뮬레이션
Queue<Integer> onStair = new LinkedList<>(); // 계단에 있는 사람들의 완료 시간 저장
int time = 0;
int finishedCount = 0;
int totalToProcess = arrivalTimes.size();
if (totalToProcess == 0)
continue;
while (finishedCount < totalToProcess || !onStair.isEmpty()) {
time++;
// 1. 계단에서 나갈 사람 처리 (현재 시간이 완료 시간인 경우)
while (!onStair.isEmpty() && onStair.peek() == time) {
onStair.poll();
finishedCount++;
}
// 2. 계단에 들어올 사람 처리
while (!arrivalTimes.isEmpty() && arrivalTimes.peek() < time && onStair.size() < 3) {
arrivalTimes.poll();
onStair.add(time + stair.length); // 현재 시간 + 계단 길이 = 완료 시간
}
}
totalMax = Math.max(totalMax, time);
}
return totalMax;
}
}