@시뮬레이션
처음에 문제 보고 이건 도대체 어떻게 구현해야하나 멘붕왔었는데 결국에 어찌어찌해서 풀었다.
방법 떠올리기도 힘들었음..
근데 로직 생각 + 구현은 1시간 반정도 걸렸는데
디버깅 하는데 2시간 반정도 걸렸다..ㅎㅎ
대환장 파티였음
문제 링크
https://swexpertacademy.com/main/code/problem/problemDetail.do
SW Expert Academy
SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!
swexpertacademy.com
논리 흐름
1. 일단 처음에는 bfs로 지도를 이동해가면서 풀어야하나 고민했다. 근데 bfs로 하면 방향을 종잡을수도 없고, 겹치는 것도 생각해야하고, 멀리 돌아가는 경우도 생길 것 같아서 접었다. 사실 이거 구현할 자신이 없어서 포기했다.
2. 그래서 계단과 사람과의 거리를 배열이나 리스트에 넣어놓고 하나씩 빼는걸 고려했는데, 겹치는 경우가 생기면 어쩌지 해서 고민했다.
근데 잘 생각해보면, 겹친다는건 가까운 계단을 두고 먼 계단에서 온다는 뜻인데, 그럼 어차피 비효율적인 거니까 걸러질 거라고 생각했다. (근데 먼 계단이 내려가는 시간이 더 짧으면 어떻게 되지..?)
헷갈렸던 점
여기서 입구에도 최대 3명까지만 있을 수 있다는 뜻인 줄 알고, 입구에 3명이 기다리고 있으면 새로 진입 못하고 기다리는 줄 알았다. 근데 입구 != 계단 위(계단을 내려가고있는 상태) 여서 계단 입구에 기다리고 있는 인원은 따로 고려할 필요가 없었다.
그리고 사람이 이동 중에 겹치면 어쩌지 했는데, 겹쳐도 상관없다. 문제에 겹치면 안된다는 조건이 애초에 없다!
다 풀때까지도 몰랐다가, 풀이방법 질문 할 때 그제서야 알았다..ㅠㅠㅠㅠㅠ
구현 방법
1. for(전체 다 계단1번을 이용할때~계단 1번을 아무도 이용안할때) 로 돌리면서 넥퍼를 변형해서 계단 1번, 2번을 이용할 사용자를 분배해준다.
2. while문을 돌리면서 1분당 사람들의 움직임을 체크한다
3. 계단에 도착했을 때, 계단을 내려가고 있는 사람들 수를 체크하고 계단에 넣을지를 결정한다.
+ 리스트를 이용할 때, 앞에서부터 지워주면 뒷부분 인덱스가 꼬여서 잘못 삭제될 수 있다. 그래서 끝에서부터 지웠다!
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;
public class Solution {
private static int N, personNum, minMinute, stairEndPersonNum, map[][], number[], person[][], stair1[], stair2[];
private static ArrayList<Integer> stairList1, stairList2, list1, list2;
private static boolean[] isRemove1, isRemove2;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
StringBuilder sb = new StringBuilder();
int T = Integer.parseInt(br.readLine());
for (int t = 1; t <= T; t++) {
N = Integer.parseInt(br.readLine());
map = new int[N][N];
personNum = 0;
minMinute = Integer.MAX_VALUE;
stair1 = new int[3];
stair2 = new int[3];
boolean isStair1 = false;
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) {
personNum++;
} else if (map[i][j] > 1) {
if (!isStair1) {
stair1[0] = i; stair1[1] = j; stair1[2] = map[i][j];
isStair1 = true;
} else {
stair2[0] = i; stair2[1] = j; stair2[2] = map[i][j];
}
}
}
}
person = new int[personNum][4];
personNum = 0;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (map[i][j] == 1) {
person[personNum][0] = i;
person[personNum][1] = j;
person[personNum][2] = Math.abs(stair1[0] - i) + Math.abs(stair1[1] - j);
person[personNum][3] = Math.abs(stair2[0] - i) + Math.abs(stair2[1] - j);
personNum++;
}
}
}
number = new int[personNum];
for (int i = 0; i <= personNum; i++) {
Arrays.fill(number, 0);
Arrays.fill(number, personNum - i, personNum, 1);
do {
stairEndPersonNum = 0;
list1 = new ArrayList<>();
list2 = new ArrayList<>();
stairList1 = new ArrayList<>();
stairList2 = new ArrayList<>();
personAssign();
stairMove();
} while (nextCombination());
}
sb.append("#" + t + " " + ++minMinute + "\n");
}
System.out.println(sb);
}
private static void stairDown() {
isRemove1 = new boolean[stairList1.size()];
isRemove2 = new boolean[stairList2.size()];
int temp = stairNumCheck(1);
for (int i = 0; i < stairList1.size(); i++) {
if (stairList1.get(i) == 0) {
if (temp > 0) {
stairList1.set(i, stairList1.get(i) + 1);
temp--;
}
} else {
stairList1.set(i, stairList1.get(i) + 1);
if (stairList1.get(i) == stair1[2]) {
isRemove1[i] = true;
stairEndPersonNum++;
}
}
}
temp = stairNumCheck(2);
for (int i = 0; i < stairList2.size(); i++) {
if (stairList2.get(i) == 0) {
if (temp > 0) {
stairList2.set(i, stairList2.get(i) + 1);
temp--;
}
} else {
stairList2.set(i, stairList2.get(i) + 1);
if (stairList2.get(i) == stair2[2]) {
isRemove2[i] = true;
stairEndPersonNum++;
}
}
}
listRemove(isRemove1, stairList1);
listRemove(isRemove2, stairList2);
}
private static void stairMove() {
int minute = 0;
while (true) {
minute++;
isRemove1 = new boolean[list1.size()];
isRemove2 = new boolean[list2.size()];
for (int i = 0; i < list1.size(); i++) {
list1.set(i, list1.get(i) - 1);
if (list1.get(i) == 0) {
isRemove1[i] = true;
stairList1.add(-1);
}
}
for (int i = 0; i < list2.size(); i++) {
list2.set(i, list2.get(i) - 1);
if (list2.get(i) == 0) {
isRemove2[i] = true;
stairList2.add(-1);
}
}
listRemove(isRemove1, list1);
listRemove(isRemove2, list2);
stairDown();
if (stairEndPersonNum == personNum) {
if (minMinute > minute)
minMinute = minute;
return;
}
}
}
private static int stairNumCheck(int num) {
int count = 0;
if (num == 1) {
for (int i = 0; i < stairList1.size(); i++)
if (stairList1.get(i) > 0 && stairList1.get(i) < stair1[2])
count++;
} else {
for (int i = 0; i < stairList2.size(); i++)
if (stairList2.get(i) > 0 && stairList2.get(i) < stair2[2])
count++;
}
return 3 - count;
}
private static void listRemove(boolean[] isRemove, ArrayList<Integer> list) {
if (list.size() >= 1)
for (int i = isRemove.length - 1; i >= 0; i--)
if (isRemove[i]) list.remove(i);
}
private static void personAssign() {
for (int i = 0; i < personNum; i++) {
if (number[i] == 0)
list1.add(person[i][2]);
else if (number[i] == 1)
list2.add(person[i][3]);
}
Collections.sort(list1);
Collections.sort(list2);
}
private static boolean nextCombination() {
int i = personNum - 1;
while (i > 0 && number[i - 1] >= number[i]) --i;
if (i == 0) return false;
int j = personNum - 1;
while (number[i - 1] >= number[j]) --j;
swap(i - 1, j);
j = personNum - 1;
while (i < j) swap(i++, j--);
return true;
}
private static void swap(int i, int j) {
int temp = number[i];
number[i] = number[j];
number[j] = temp;
}
}
삽질 포인트
1. list1, list2를 이용하다보니.. 2를 써야하는곳에 1을 써서 계속 틀렸다.
2. return문을 minMinute가 갱신될때의 if문 안에 넣어놔서.. 갱신이 안되면 무한루프가 돌아서 이거 잡느라 1시간 넘게 썼다ㅠ
다 짜니까 200줄 넘게 나왔다.
이렇게 길게 짠 적은 별로 없었는데 디버깅하느라 너무 힘들었다.
코드를 간략하게 짜는 연습이 필요할 것 같다.
끝!
'algorithm > SW Expert Academy' 카테고리의 다른 글
| [SWEA] 1949.등산로 조성 (java) / DFS (0) | 2020.01.25 |
|---|---|
| [SWEA] 2382.미생물 격리 (java) / 시뮬레이션, BFS (0) | 2020.01.25 |
| [SWEA] 2477.차량 정비소 / 시뮬레이션 (0) | 2020.01.15 |
| [SWEA] 4013.특이한 자석 / 시뮬레이션 (0) | 2020.01.09 |
| [SWEA] 5653.줄기세포배양 / BFS, 시뮬레이션 (0) | 2020.01.08 |
댓글