문제
문제 설명
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번 계단을 통해 이동
제한 사항
입출력 예
| 입력 | 출력 |
|---|---|
| 1 | |
| 5 | |
| 0 1 1 0 0 | |
| 0 0 1 0 3 | |
| 0 1 0 1 0 | |
| 0 0 0 0 0 | |
| 1 0 5 0 0 | #1 9 |
제출 코드
package com.example.javacodingtest.swea;
import java.io.*;
import java.util.LinkedList;
import java.util.List;
import java.util.StringTokenizer;
/*
@author ranuinclulus
@since 2024.08.29
@link
@timecomplex
@performance 29640 KB, 216 MB
@category
@note
*/
public class none2383 {
class Stair {
int row;
int col;
int length;
public Stair(int row, int col, int length) {
this.row = row;
this.col = col;
this.length = length;
}
}
class Person {
int row;
int col;
int distance;
public Person(int row, int col) {
this.row = row;
this.col = col;
this.distance = 0;
}
}
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
static StringTokenizer st;
static StringBuilder sb = new StringBuilder();
static List<Person> people;
static List<Stair> stairs;
static final int MAX_PEOPLE = 3;
static List<Person> stairOne;
static List<Person> stairTwo;
static int testNum;
static int n;
static int minTime;
public void solution() throws IOException {
testNum = Integer.parseInt(br.readLine());
for (int test = 1; test <= testNum; test++) {
n = Integer.parseInt(br.readLine());
people = new LinkedList<>();
stairs = new LinkedList<>();
for (int i = 0; i < n; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < n; j++) {
int val = Integer.parseInt(st.nextToken());
if (val == 1) people.add(new Person(i, j));
if (val != 1 && val != 0) stairs.add(new Stair(i, j, val));
}
}
minTime = Integer.MAX_VALUE;
usingStair(0, 0);
sb.append("#").append(test).append(" ").append(minTime).append('\n');
}
bw.write(sb.toString());
bw.flush();
}
private void usingStair(int depth, int bitMask) throws IOException {
if (depth == people.size()) {
calculateDistance(bitMask);
return;
}
usingStair(depth + 1, bitMask);
usingStair(depth + 1, bitMask | (1 << depth));
}
private void calculateDistance(int bitMask) throws IOException {
stairOne = new LinkedList<>();
stairTwo = new LinkedList<>();
for (int i = 0; i < people.size(); i++) {
Person person = people.get(i);
if ((bitMask & (1 << i)) == 0) { // 첫 번째 계단 이용
Stair stair = stairs.get(0);
person.distance = Math.abs(person.row - stair.row) + Math.abs(person.col - stair.col);
stairOne.add(person);
} else {
Stair stair = stairs.get(1);
person.distance = Math.abs(person.row - stair.row) + Math.abs(person.col - stair.col);
stairTwo.add(person);
}
}
stairOne.sort((o1, o2) -> o1.distance - o2.distance);
stairTwo.sort((o1, o2) -> o1.distance - o2.distance);
moveStair();
}
private void moveStair() {
for (int i = 0; i < stairOne.size(); i++) {
if (i < MAX_PEOPLE) { // 세 명 미만이면
stairOne.get(i).distance += stairs.get(0).length;
} else { // 세 명 이상이면
if (stairOne.get(i - 3).distance > stairOne.get(i).distance) { // 대기 시간이 발생하는 경우
stairOne.get(i).distance = stairOne.get(i - 3).distance + stairs.get(0).length;
} else {
stairOne.get(i).distance += stairs.get(0).length;
}
}
}
for (int i = 0; i < stairTwo.size(); i++) {
if (i < MAX_PEOPLE) { // 세 명 미만이면
stairTwo.get(i).distance += stairs.get(1).length;
} else { // 세 명 이상이면
if (stairTwo.get(i - 3).distance > stairTwo.get(i).distance) { // 대기 시간이 발생하는 경우
stairTwo.get(i).distance = stairTwo.get(i - 3).distance + stairs.get(1).length;
} else {
stairTwo.get(i).distance += stairs.get(1).length;
}
}
}
calculateMinTime();
}
private void calculateMinTime() {
int stairOneTime = (!stairOne.isEmpty()) ? stairOne.get(stairOne.size() - 1).distance : 0;
int stairTwoTime = (!stairTwo.isEmpty()) ? stairTwo.get(stairTwo.size() - 1).distance : 0;
int resultTime = Math.max(stairOneTime, stairTwoTime) + 1;
minTime = Math.min(minTime, resultTime);
}
public static void main(String[] args) throws IOException {
new none2383().solution();
}
}아이디어
- 일단 사람들이 어떤 계단을 이용할지 배정하자 → 비트마스킹 활용
- 계단 이용이 배정되었다면 거리를 계산해서 들고 있자
- 거리가 가까운 애들부터 계단을 이용하도록 정렬
- 실제로 계단을 이용하는 과정 구현
객체 및 변수 설명
Stair
- 계단의 위치와 길이를 저장하는 객체
Person
- 사람의 위치와 해당 사람이 어떤 계단으로 이동하기로 결정되었을 때, 계단까지 가는 거리를 저장하는 객체
변수 설명
people: 총 이동해야 하는 사람들을 List로 저장stairs: 첫 번째 계단을 0에, 두 번째 계단을 1에- 그냥 뒀지만
stair1,stair2로 두고 딱히 배열이나 리스트로 관리하지 않아도 될 것 같음 - 계단은 무조건 두 개이기 때문
- 그냥 뒀지만
stairOne: 첫 번째 계단을 이용하기로 결정된 사람들의 모임stairTwo: 두 번째 계단을 이용하기로 결정된 사람들의 모임
풀이 과정 설명
비트마스킹을 이용해 계단을 이용하는 경우 부분집합 구하기
- 예를 들어 6명의 사람이 있을 때 bitMask가 8이라면
- 8 → 000100
사람 이용하는 계단 1 1 2 1 3 2 4 1 5 1 6 1 - 조합을 다 구했다면 거리를 계산하는
calculateDistance()함수 실행
계단 이용을 배정하고 거리 구하기
stairOne: 첫 번째 계단을 이용하기로 결정된 사람들의 모임stairTwo: 두 번째 계단을 이용하기로 결정된 사람들의 모임- 첫 번째 계단을 이용하는 경우 사람의 거리를 갱신한 뒤
stairOne에 삽입 - 두 번째 계단을 이용하는 경우 사람의 거리를 갱신한 뒤
stairTwo에 삽입 - 이후 거리가 가장 짧은 애들이 앞에 오도록 정렬
- 이 과정을 모든 조합에 대해서 수행하는 것
- 첫 번째 테스트케이스에 대한 예시
비트마스크가 100001일 때 계단 1을 이용하는 사람들 Person{row=1, col=2, distance=2} Person{row=2, col=3, distance=2} Person{row=0, col=2, distance=3} Person{row=2, col=1, distance=4} 계단 2을 이용하는 사람들 Person{row=4, col=0, distance=2} Person{row=0, col=1, distance=5} ================================ 비트마스크가 10001일 때 계단 1을 이용하는 사람들 Person{row=1, col=2, distance=2} Person{row=0, col=2, distance=3} Person{row=2, col=1, distance=4} Person{row=4, col=0, distance=7} 계단 2을 이용하는 사람들 Person{row=2, col=3, distance=3} Person{row=0, col=1, distance=5} ================================ 비트마스크가 110001일 때 계단 1을 이용하는 사람들 Person{row=1, col=2, distance=2} Person{row=0, col=2, distance=3} Person{row=2, col=1, distance=4} 계단 2을 이용하는 사람들 Person{row=4, col=0, distance=2} Person{row=2, col=3, distance=3} Person{row=0, col=1, distance=5}
각 계단에 대해 dp처럼 시간을 계산해 보기
- 너무 크니까 계단 1만 잘라서 살펴볼게요
- 계단 1에 배치된 사람들에 대해 순회하면서
- 만약 1, 2, 3번째로 거리가 짧은 사람들이라면 → 계단은 초기화 상태로 비어 있기 때문에 올라갈 수 있음
- 올라감
- 올라간 사람의 거리 = 계단까지 오는 데 걸린 거리 + 계단의 길이가 되는 것
- 4 번째 사람부터는 대기가 발생하는지 아닌지 생각해 봐야 함
- 예를 들어 4번째 사람이 계단 1까지 가는 시간이 3인데 3번째 전 사람이 계단 마지막 칸까지 가는 시간이 6이면
- 3이라는 대기 시간이 발생한 뒤 3번째 전 사람이 내려가자마자 계단에 올라갈 수 있음 ㅜㅜ
- 즉 계단까지 가는 시간 3 + 대기 시간 3 + 계단의 길이가 지나야 4번째 사람은 내려올 수 있음
- 어차피 대기해야 하기 때문에 3번째 전 사람이 내려가는 시간이랑 똑같음
- 거리가 업데이트되면 최종 값 구하러 고고
최종 값 구하기
- 마지막으로 지난 사람의 거리가 최종 값임
- 마지막으로 지나간 사람이 계단 1에 있을 수도 있고 계단 2에 있을 수도 있어서 empty()라면 0으로 하고, 비어 있지 않다면 마지막에 계단을 지나는 사람의 거리로 업데이트
- 두 계단 중 최대값이 이동하는 최종 시간임
- 마지막 인간이 내려오는 시간 +1 필요 ^^
- 최종 시간의 최솟값으로 업데이트
질문을 위한 망한 코드
import java.io.*;
import java.util.LinkedList;
import java.util.List;
import java.util.StringTokenizer;
/*
@author ranuinclulus
@since 2024.08.29
@link
@timecomplex
@performance
@category
@note
*/
public class none2383 {
//TODO isFull 다시 고민하기
class Stair {
int row;
int col;
int length;
int[] capacities;
public Stair(int row, int col, int length) {
this.row = row;
this.col = col;
this.length = length;
this.capacities = new int[length + 1];
}
public void addPerson() {
capacities[0]++;
}
public void move() {
for (int i = length; i >= 1; i--) {
capacities[i] = capacities[i - 1];
}
capacities[0] = 0;
}
public boolean canUse() {
int totalUse = 0;
for (int i = 0; i <= length; i++) {
totalUse += capacities[i];
}
return totalUse < MAX_PEOPLE;
}
}
class Person {
int row;
int col;
public Person(int row, int col) {
this.row = row;
this.col = col;
}
}
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
static StringTokenizer st;
static StringBuilder sb = new StringBuilder();
static List<Person> people;
static List<Stair> stairs;
static int testNum;
static int n;
static final int MAX_PEOPLE = 3;
static List<int[]> distances;
static int minTime;
public void solution() throws IOException {
testNum = Integer.parseInt(br.readLine());
for (int test = 1; test <= testNum; test++) {
n = Integer.parseInt(br.readLine());
people = new LinkedList<>();
stairs = new LinkedList<>();
for (int i = 0; i < n; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < n; j++) {
int val = Integer.parseInt(st.nextToken());
if (val == 1) people.add(new Person(i, j));
if (val != 1 && val != 0) stairs.add(new Stair(i, j, val));
}
}
minTime = Integer.MAX_VALUE;
usingStair(0, 0);
sb.append("#").append(test).append(" ").append(minTime).append('\n');
}
bw.write(sb.toString());
bw.flush();
}
private void usingStair(int depth, int bitMask) throws IOException {
if (depth == people.size()) {
calculateDistance(bitMask);
return;
}
usingStair(depth + 1, bitMask);
usingStair(depth + 1, bitMask | (1 << depth));
}
private void calculateDistance(int bitMask) throws IOException {
distances = new LinkedList<>();
for (int i = 0; i < people.size(); i++) {
Person person = people.get(i);
if ((bitMask & (1 << i)) == 0) { // 첫 번째 계단 이용
Stair stair = stairs.get(0);
int distance = Math.abs(person.row - stair.row) + Math.abs(person.col - stair.col);
distances.add(new int[] {0, distance});
} else {
Stair stair = stairs.get(1);
int distance = Math.abs(person.row - stair.row) + Math.abs(person.col - stair.col);
distances.add(new int[] {1, distance});
}
}
System.out.println();
distances.sort((o1, o2) -> o1[1] - o2[1]);
moveStair();
}
private void moveStair() {
int time = 0;
while (!allClear() || !allEmpty()) {
time++;
// 시간이 지나면 게단 하나씩 이동하기
for (Stair stair : stairs) {
stair.move();
}
for(int[] distance : distances) {
if (distance[0] == -1) continue;
distance[1]--;
if (distance[1] == 0) {
if (!stairs.get(distance[0]).canUse()) {
distance[1]++;
continue;
}
stairs.get(distance[0]).addPerson();
distance[0] = -1;
}
}
}
minTime = Math.min(minTime, time);
}
// 계단이 모두 비었는지
private boolean allEmpty() {
for(Stair stair : stairs) {
for (int i = 0; i <= stair.length; i++) {
if (stair.capacities[i] != 0) return false;
}
}
return true;
}
// 모두 -1번 계단을 이용하면 다 통과했다
private boolean allClear() {
for (int[] distance : distances) {
if (distance[0] != -1) return false;
}
return true;
}
public static void main(String[] args) throws IOException {
new none2383().solution();
}
}
/*
1
9
0 0 0 1 0 0 0 0 0
0 1 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 8
7 0 0 0 0 1 0 0 0
0 0 0 0 0 1 1 0 0
0 0 0 0 0 0 0 0 0
1 0 0 0 0 1 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
*/
/*
#1 9
#2 8
#3 9
#4 7
#5 8
#6 8
#7 11
#8 11
#9 18
#10 12
*/