import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;
import java.util.StringTokenizer;
class Stair {
int y, x; // 계단의 위치
int cost; // 계단 내려가는데 걸리는 시간
int[] state; // 내려가는 정도
Person[] seat; // 계단 위에 있는 사람들
Queue<Person> inQueue; // 계단 입구
Queue<Person> outQueue; // 계단 출구
public Stair(int y, int x, int cost) {
this.y = y;
this.x = x;
this.cost = cost;
seat = new Person[3];
state = new int[3];
}
public void tick() {
// 작업량 감소 (계단 오르는 비용)
for (int i = 0; i < seat.length; i++) {
if (state[i] != 0 && seat[i] != null) {
state[i]--;
}
}
}
// 계단에서 나간다.
public void comeOut() {
for (int i = 0; i < seat.length; i++) {
if (state[i] == 0 && seat[i] != null) {
outQueue.offer(seat[i]);
seat[i] = null;
}
}
}
// 계단으로 들어온다.
public void comeIn() {
for (int i = 0; i < 3; i++) {
if (seat[i] == null) {
seat[i] = inQueue.poll();
state[i] = cost;
}
}
}
}
class Person {
int y, x;
int time;
int where;
public Person(int y, int x) {
this.y = y;
this.x = x;
}
}
class Solution {
static boolean Debug = false;
private static int T;
private static int MapSize;
private static ArrayList<Person> pList;
private static Stair[] Stair;
private static int PersonSize;
private static int MinTime;
public static void main(String args[]) throws Exception {
BufferedReader br;
if (Debug) {
File f = new File("디렉토리", "sample_input (9).txt");
FileReader reader = new FileReader(f);
br = new BufferedReader(reader);
} else {
br = new BufferedReader(new InputStreamReader(System.in)); // 직접입력시 이용
}
StringTokenizer st;
int TestSize = Integer.parseInt(br.readLine());
for (T = 1; T <= TestSize; T++) {
MapSize = Integer.parseInt(br.readLine());
pList = new ArrayList<>();
Stair = new Stair[2];
// [Input] 사람 객체를 생성하고 계단 객체를 생성한다.
for (int i = 0; i < MapSize; i++) {
st = new StringTokenizer(br.readLine());
int what;
for (int j = 0; j < MapSize; j++) {
what = Integer.parseInt(st.nextToken());
// 1. 사람이라면
if (what == 1) {
pList.add(new Person(i, j));
} else if (what > 1) { // 2.계단이라면
if (Stair[0] == null) {
Stair[0] = new Stair(i, j, what);
} else if (Stair[1] == null) {
Stair[1] = new Stair(i, j, what);
}
} else {
// Non-target
}
}
}
PersonSize = pList.size();
MinTime = Integer.MAX_VALUE;
// bitmask 값은 각 사람이 어떤 출구로 이동할까를 뜻한다.
for (int i = 0; i < (1 << PersonSize); i++) {
// 각 사람에게 위치와 시간을 지정
schedule(i);
// 시뮬레이션
simulate();
}
System.out.println(String.format("#%d %d", T, MinTime));
}
}
private static void simulate() {
// 0번 계단 입구, 1번 계단 입구, 출구
Queue<Person> Robby0, Robby1, Robby2;
Robby0 = new LinkedList<>();
Robby1 = new LinkedList<>();
Robby2 = new LinkedList<>();
// 계단의 입구와 출구 지정
Stair[0].inQueue = Robby0;
Stair[1].inQueue = Robby1;
Stair[0].outQueue = Robby2;
Stair[1].outQueue = Robby2;
ArrayList<Person> personList = new ArrayList<>();
personList.addAll(pList); // 출입 명단
Stack<Person> dStack = new Stack(); // 출입한 사람은 출입 명단에서 제거
int Timer = -1;
while (Robby2.size() != PersonSize) {
Timer++;
// 사람을 계단입구로 등장시킨다.
for (Person p : personList) {
if (p.time == Timer) {
if (p.where == 0) {
Robby0.offer(p);
} else if (p.where == 1) {
Robby1.offer(p);
}
dStack.add(p);
}
}
// 등장인물 리스트에서 제거
if (!dStack.isEmpty()) {
for (Person p : dStack) {
personList.remove(p);
}
dStack.clear();
}
Stair[0].tick(); // 작업량 감소
Stair[0].comeOut(); // 계단에서 나감
Stair[0].comeIn(); // 계단에 입장
Stair[1].tick();
Stair[1].comeOut();
Stair[1].comeIn();
}
if (MinTime > Timer) {
MinTime = Timer;
}
}
public static void schedule(int bitmask) {
// 상황(bitmask)에 따라서 Person 객체에 시간과 장소를 부여
int y0, x0, y1, x1;
y0 = Stair[0].y;
x0 = Stair[0].x;
y1 = Stair[1].y;
x1 = Stair[1].x;
Person person;
for (int i = 0; i < PersonSize; i++) {
person = pList.get(i);
if ((bitmask & (1 << i)) == 0) {
person.time = getTime(person, y0, x0);
person.where = 0;
// log("0번 출구로 %d만큼의 시간이 걸렸다.", person.time);
} else {
person.time = getTime(person, y1, x1);
person.where = 1;
// log("1번 출구로 %d만큼의 시간이 걸렸다.", person.time);
}
}
}
// xy 지점까지 가는 데 걸리는 시간
public static int getTime(Person p, int y, int x) {
// 계단 입구에 도착하고 1분 후에 내려간다. (1 + 이동시간)
return 1 + (p.x - x > 0 ? p.x - x : x - p.x) + (p.y - y > 0 ? p.y - y : y - p.y);
}
public static void log(String input) {
if (Debug) {
System.out.println(input);
}
}
public static void log(String input, Object... args) {
if (Debug) {
System.out.println(String.format(input, args));
}
}
}
'Knowledge > 알고리즘' 카테고리의 다른 글
1953. [모의 SW 역량테스트] 탈주범 검거 (0) | 2017.10.15 |
---|---|
2105. [모의 SW 역량테스트] 디저트 카페 (0) | 2017.10.15 |
2477. [모의 SW 역량테스트] 차량 정비소 (0) | 2017.10.10 |
1259. [S/W 문제해결 응용] 7일차 - 금속막대 (0) | 2017.10.08 |
2117. [모의 SW 역량테스트] 홈 방범 서비스 (0) | 2017.10.07 |