import java.io.BufferedReader;

import java.io.File;

import java.io.FileReader;

import java.io.InputStreamReader;

import java.util.ArrayList;

import java.util.StringTokenizer;


class Virus {

int y, x;


public Virus(int y, int x) {

this.y = y;

this.x = x;

}

}


class Wall {

int y, x;


public Wall(int y, int x) {

this.y = y;

this.x = x;

}

}


public class Main {


private static boolean Debug = true;

private static int MapSize_Y;

private static int MapSize_X;

private static int[][] Map;

private static int[][] Visited;

private static ArrayList<Virus> vList;

private static ArrayList<Wall> wList;

private static int MaxSafeCount;

private static int OriginSafeCount;

private static int VirusCount;


public static void main(String[] args) throws Exception {


BufferedReader br;

StringTokenizer st;


if (Debug && false) {

File f = new File("C:\\Users\\wvimi\\Downloads", "sample_input (11).txt");

FileReader reader = new FileReader(f);

br = new BufferedReader(reader);

} else {

br = new BufferedReader(new InputStreamReader(System.in)); // 직접입력시 이용

}


// 맵 크기

st = new StringTokenizer(br.readLine());

MapSize_Y = Integer.parseInt(st.nextToken());

MapSize_X = Integer.parseInt(st.nextToken());


vList = new ArrayList<>();

wList = new ArrayList<>();

OriginSafeCount = 0;

// 맵 읽기

int atom;

Map = new int[MapSize_Y][];

Visited = new int[MapSize_Y][];

for (int i = 0; i < MapSize_Y; i++) {

st = new StringTokenizer(br.readLine());

Map[i] = new int[MapSize_X];

Visited[i] = new int[MapSize_X];

for (int j = 0; j < MapSize_X; j++) {

atom = Integer.parseInt(st.nextToken());

Map[i][j] = atom;

if (atom == 2) {

vList.add(new Virus(i, j));

OriginSafeCount++;

} else if(atom==0) {

wList.add(new Wall(i, j));

OriginSafeCount++;

}

}

}


MaxSafeCount = 0;

makeWall();

System.out.println(MaxSafeCount);

}


private static void makeWall() {

int wsize = wList.size();


Wall w1, w2, w3;

for (int i = 0; i < wsize; i++) {

for (int j = i + 1; j < wsize; j++) {

for (int k = j + 1; k < wsize; k++) {

w1 = wList.get(i);

w2 = wList.get(j);

w3 = wList.get(k);

Map[w1.y][w1.x] = 1;

Map[w2.y][w2.x] = 1;

Map[w3.y][w3.x] = 1;


simulate();


Map[w1.y][w1.x] = 0;

Map[w2.y][w2.x] = 0;

Map[w3.y][w3.x] = 0;

}

}

}


}


private static void simulate() {


// 조건 초기화

Visited = new int[MapSize_Y][];

for (int i = 0; i < MapSize_Y; i++) {

Visited[i] = new int[MapSize_X];

}

// log("s:%d, w:%d, v:%d", countMap(0), countMap(1), countMap(2));


VirusCount = 0;

int y, x;

for (Virus item : vList) {

y = item.y;

x = item.x;


if (Visited[y][x] == 0) {

findPath(y, x);

} else {

// Non-target

}

}


// log("s1:%d, w:%d, v:%d", countMap(0), countMap(1), countMap(2));

int safeCount = countMap(0);

if (MaxSafeCount < safeCount) {

MaxSafeCount = safeCount;

}


}


static int[] rotY = { 1, 0, -1, 0};

static int[] rotX = { 0, 1, 0, -1};


private static void findPath(int y, int x) {

Visited[y][x] = 1;

VirusCount++;

if(OriginSafeCount - VirusCount < MaxSafeCount) {

// break; 조건

return;

}

int moveY, moveX;

for (int i = 0; i < 4; i++) {


moveY = y + rotY[i];

moveX = x + rotX[i];


if (isRight(moveY, moveX)) {

findPath(moveY, moveX);

}

}


}


private static boolean isRight(int y, int x) {


if (y < 0 || y >= MapSize_Y || x < 0 || x >= MapSize_X) {

return false;

} else if (Visited[y][x] == 1 || Map[y][x] == 1) {

return false;

}


return true;

}


private static int countMap(int what) {


int count = 0;

for (int i = 0; i < MapSize_Y; i++) {

for (int j = 0; j < MapSize_X; j++) {


if (what == 0) { // 빈공간의 수

if (Visited[i][j] == 0 && Map[i][j] == 0) {

count++;

}

} else if (what == 1) { // 벽의 수

if (Map[i][j] == 1) {

count++;

}

} else if (what == 2) { // 바이러스 영역의 수

if (Visited[i][j] == 1 || Map[i][j] == 2) {

count++;

}

}

}

}


return count;

}


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 > 알고리즘' 카테고리의 다른 글

백준 3190번: 뱀  (0) 2017.10.19
백준 14499번: 주사위 굴리기  (0) 2017.10.19
백준 14502번: 연구소  (0) 2017.10.17
백준 14501번: 퇴사  (0) 2017.10.17
백준 13458번: 시험 감독  (0) 2017.10.17
백준: 14503번: 로봇 청소기  (0) 2017.10.17

import java.io.BufferedReader;

import java.io.File;

import java.io.FileReader;

import java.io.InputStreamReader;

import java.util.StringTokenizer;


class Schedule {

int cost, pay;


public Schedule(int cost, int pay) {

this.cost = cost;

this.pay = pay;

}

}


public class Main {


private static boolean Debug = false;

private static int DateLen;

private static Schedule[] Date;

private static int MaxPayment;


public static void main(String[] args) throws Exception {


BufferedReader br;

StringTokenizer st;


if (Debug && false) {

File f = new File("C:\\Users\\wvimi\\Downloads", "sample_input (11).txt");

FileReader reader = new FileReader(f);

br = new BufferedReader(reader);

} else {

br = new BufferedReader(new InputStreamReader(System.in)); // 직접입력시 이용

}


// 일정의 길이

DateLen = Integer.parseInt(br.readLine());

Date = new Schedule[DateLen];


// 일정 읽기

for (int i = 0; i < DateLen; i++) {

st = new StringTokenizer(br.readLine());

Date[i] = new Schedule(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));

}


MaxPayment = -1;

checkDate(0, 0);


System.out.println(MaxPayment);

}


private static void checkDate(int index, int sum) {


int cost = Date[index].cost;

int pay = Date[index].pay; 


int next = index + cost;


log("checkDate(%d) sum (%d) next(%d)", index, sum, next);


// 오늘 일정을 사용하고, 다음 일정으로 옮긴다.

if (next < DateLen) {

checkDate(next, sum + pay);

}


// 오늘 일정을 사용하지 않는 경우, 다음 일정으로 옮긴다. (단, 하루짜리 일정은 무조건 체킹)

if (cost != 1 && index + 1 < DateLen) {

checkDate(index + 1, sum);

}


int payment = (next <= DateLen ? sum + pay : sum);

log("최종금액: %d   sum: %d   next: %d", payment, sum, next);

if (MaxPayment < payment) {

MaxPayment = payment;

}


}



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 > 알고리즘' 카테고리의 다른 글

백준 14499번: 주사위 굴리기  (0) 2017.10.19
백준 14502번: 연구소  (0) 2017.10.17
백준 14501번: 퇴사  (0) 2017.10.17
백준 13458번: 시험 감독  (0) 2017.10.17
백준: 14503번: 로봇 청소기  (0) 2017.10.17
1953. [모의 SW 역량테스트] 탈주범 검거  (0) 2017.10.15

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80


import java.io.BufferedReader;

import java.io.File;

import java.io.FileReader;

import java.io.InputStreamReader;

import java.util.StringTokenizer;


public class Main {


private static boolean Debug = false;

private static int MapSize_Y;

private static int MapSize_X;

private static int[][] Map;

private static int[][] Visited;


public static void main(String[] args) throws Exception {


BufferedReader br;

if (Debug && false) {

File f = new File("C:\\Users\\wvimi\\Downloads", "sample_input (11).txt");

FileReader reader = new FileReader(f);

br = new BufferedReader(reader);

} else {

br = new BufferedReader(new InputStreamReader(System.in)); // 직접입력시 이용

}


StringTokenizer st;


// 맵의 크기를 받는다.

st = new StringTokenizer(br.readLine());

MapSize_Y = Integer.parseInt(st.nextToken());

MapSize_X = Integer.parseInt(st.nextToken());


// 로봇의 위치를 받는다.

st = new StringTokenizer(br.readLine());

int startY = Integer.parseInt(st.nextToken());

int startX = Integer.parseInt(st.nextToken());

int rIndex = Integer.parseInt(st.nextToken());


// 맵 입력

Map = new int[MapSize_Y][];

Visited = new int[MapSize_Y][];

for (int i = 0; i < MapSize_Y; i++) {

st = new StringTokenizer(br.readLine());

Map[i] = new int[MapSize_X];

Visited[i] = new int[MapSize_X];

for (int j = 0; j < MapSize_X; j++) {

Map[i][j] = Integer.parseInt(st.nextToken());

}

}


moveRobot(startY, startX, rIndex);


int count = 0;

for (int i = 0; i < MapSize_Y; i++) {

for (int j = 0; j < MapSize_X; j++) {

if (Visited[i][j] == 1) {

count++;

}

}

}


System.out.println(count);

}


private static int[] rotY = { -1, 0, 1, 0 };

private static int[] rotX = { 0, 1, 0, -1 };


private static void moveRobot(int y, int x, int rIndex) {

Visited[y][x] = 1;

log("(%d,%d) 방문", y, x);


if (!isLeftClear(y, x, rIndex)) {

// Command 1

int nIndex = rIndex == 0 ? 3 : rIndex - 1;

int moveY = y + rotY[nIndex];

int moveX = x + rotX[nIndex];


moveRobot(moveY, moveX, nIndex);

} else if (!isAllClear(y, x)) {

// Command 2

int nIndex = rIndex == 0 ? 3 : rIndex - 1;

moveRobot(y, x, nIndex); // 방향 전환

} else if (isMoveBack(y, x, rIndex)) {

// Command 3

int nIndex = rIndex < 2 ? rIndex + 2 : rIndex - 2;

int moveY = y + rotY[nIndex];

int moveX = x + rotX[nIndex];

moveRobot(moveY, moveX, rIndex); // 방향은 유지한 채로 뒤로 한 발자국

} else {

// Command 4

log("I've Done");

}


}


// 로봇의 왼쪽 방향이 깨끗한지

private static boolean isLeftClear(int y, int x, int rIndex) {

int sIndex = rIndex == 0 ? 3 : rIndex - 1;

int moveY = y + rotY[sIndex];

int moveX = x + rotX[sIndex];


if (moveY < 0 || moveY >= MapSize_Y || moveX < 0 || moveX >= MapSize_X) {

return true;

} else if (Map[moveY][moveX] == 1) {

return true;

} else if (Visited[moveY][moveX] == 1) {

return true;

}


return false;

}


// 모든 방향 모두 깨끗한지

private static boolean isAllClear(int y, int x) {


for (int i = 0; i < 4; i++) {

if (!isLeftClear(y, x, i)) {

return false;

}

}


return true;

}


// 후진이 가능한지

private static boolean isMoveBack(int y, int x, int rIndex) {

int sIndex = rIndex < 2 ? rIndex - 2 + 4 : rIndex - 2;

int moveY = y + rotY[sIndex];

int moveX = x + rotX[sIndex];


if (moveY < 0 || moveY >= MapSize_Y || moveX < 0 || moveX >= MapSize_X) {

return false;

} else if (Map[moveY][moveX] == 1) {

return false;

}


return true;

}


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));

}

}


}



import java.io.BufferedReader;

import java.io.File;

import java.io.FileReader;

import java.io.InputStreamReader;

import java.util.StringTokenizer;


class Solution {


static boolean Debug = false;

private static int T;

private static int MapSize_Y;

private static int MapSize_X;

private static int FootSize;


private static int[][] Map; // 맵정보

private static int[][] Visited; // 시간정보

private static int[][] sTunnel; // 현재터널 방위측정

private static int[][] eTunnel; // 다음터널 방위측정


public static void main(String args[]) throws Exception {


BufferedReader br;

if (Debug) {

File f = new File("C:\\Users\\wvimi\\Downloads", "sample_input (11).txt");

FileReader reader = new FileReader(f);

br = new BufferedReader(reader);

} else {

br = new BufferedReader(new InputStreamReader(System.in)); // 직접입력시 이용

}


StringTokenizer st;


eTunnel = new int[8][];

eTunnel[1] = new int[] { 1, 1, 1, 1 };

eTunnel[2] = new int[] { 1, 0, 1, 0 };

eTunnel[3] = new int[] { 0, 1, 0, 1 };

eTunnel[4] = new int[] { 0, 0, 1, 1 };

eTunnel[5] = new int[] { 1, 0, 0, 1 };

eTunnel[6] = new int[] { 1, 1, 0, 0 };

eTunnel[7] = new int[] { 0, 1, 1, 0 };


sTunnel = new int[8][];

sTunnel[1] = new int[] { 1, 1, 1, 1 };

sTunnel[2] = new int[] { 1, 0, 1, 0 };

sTunnel[3] = new int[] { 0, 1, 0, 1 };

sTunnel[4] = new int[] { 1, 1, 0, 0 };

sTunnel[5] = new int[] { 0, 1, 1, 0 };

sTunnel[6] = new int[] { 0, 0, 1, 1 };

sTunnel[7] = new int[] { 1, 0, 0, 1 };


int TestSize = Integer.parseInt(br.readLine());

for (T = 1; T <= TestSize; T++) {


st = new StringTokenizer(br.readLine());

MapSize_Y = Integer.parseInt(st.nextToken());

MapSize_X = Integer.parseInt(st.nextToken());


int doorY, doorX;

doorY = Integer.parseInt(st.nextToken());

doorX = Integer.parseInt(st.nextToken());


int time = Integer.parseInt(st.nextToken());


Visited = new int[MapSize_Y][];

Map = new int[MapSize_Y][];

// Map 읽기

for (int i = 0; i < MapSize_Y; i++) {

Map[i] = new int[MapSize_X];

Visited[i] = new int[MapSize_X];

st = new StringTokenizer(br.readLine());

for (int j = 0; j < MapSize_X; j++) {

Map[i][j] = Integer.parseInt(st.nextToken());

Visited[i][j] = -1;

}

}


findPath(doorY, doorX, time - 1);

FootSize = 0;

for (int i = 0; i < MapSize_Y; i++) {

for (int j = 0; j < MapSize_X; j++) {

if (Visited[i][j] != -1) {

FootSize++;

}

}

}


System.out.println(String.format("#%d %d", T, FootSize));


}


}


static int[] rotY = { -1, 0, 1, 0 };

static int[] rotX = { 0, 1, 0, -1 };


private static void findPath(int y, int x, int time) {

Visited[y][x] = time;


if (time == 0) {

// log(String.format("타임업 - 좌표(%d, %d) 시간: %d", y, x, time));

return;

}


// log(String.format("이동중 - 좌표(%d, %d) 시간: %d", y, x, time));

boolean isLast = true;

int nextY, nextX;

for (int i = 0; i < 4; i++) {

nextY = y + rotY[i];

nextX = x + rotX[i];


// 현재 터널에서 이동 가능한지 체크!

if (sTunnel[Map[y][x]][i] == 0) {

continue;

}


// 다음 경로에 진입할 수 있는지 체크!

if (isRight(nextY, nextX, i, time)) {

findPath(nextY, nextX, time - 1);

isLast = false;

}

}


}


public static boolean isRight(int y, int x, int rIndex, int time) {


if (x < 0 || x >= MapSize_X || y < 0 || y >= MapSize_Y) {

return false; // 배열 범위초과

} else if (Map[y][x] == 0) {

return false; // 벽

} else if (eTunnel[Map[y][x]][rIndex] == 0) {

return false; // 터널 이동 불가

} else if (Visited[y][x] > time) {

// 누군가가 방문했더라면, 나보다 먼저 방문했을 땐 못가고, 내가 더 먼저라면 갈 수 있다.

// 깊이 탐색이므로 시간 순으로 방문하지 않는다. 너비 탐색이라면 알아서 시간 순 탐색이니 신경쓰지 않아도 됨.

return false;

}


return true;

}


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));

}

}


}

import java.io.BufferedReader;

import java.io.File;

import java.io.FileReader;

import java.io.InputStreamReader;

import java.util.StringTokenizer;


class Solution {


static boolean Debug = false;

private static int T;

private static int MapSize;

private static int[][] Map;

private static int MaxSize;

private static int DesertMaxNo;


public static void main(String args[]) throws Exception {


BufferedReader br;

if (Debug) {

File f = new File("C:\\Users\\wvimi\\Downloads", "sample_input (10).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());

Map = new int[MapSize][];

DesertMaxNo = -1; 


// Map 읽기

for (int i = 0; i < MapSize; i++) {

Map[i] = new int[MapSize];

st = new StringTokenizer(br.readLine());

for (int j = 0; j < MapSize; j++) {

Map[i][j] = Integer.parseInt(st.nextToken());

if(Map[i][j]>DesertMaxNo) {

DesertMaxNo = Map[i][j];

}

}

}


MaxSize = -1;

findPath();


System.out.println(String.format("#%d %d", T, MaxSize));


}


}


private static void findPath() {


int y, x;

for (int XY = 0; XY < MapSize * MapSize; XY++) {

// 모든 좌표 탐색


y = XY / MapSize;

x = XY % MapSize;


// 최대 이동범위 구하기 (왼쪽, 오른쪽)

int maxLeft = x;

int maxRight = (MapSize - 1) - x;


for (int i = maxLeft; i > 0; i--) {

for (int j = maxRight; j > 0; j--) {


// 수직크기 측정 (맵의 범위를 벗어나지 않도록)

if (i + j + y >= MapSize) {

continue;

}


// 해당 움직임의 디저트수

int eatSize = (i + j) * 2;

if (MaxSize < eatSize) {

// 더 작은 사이즈는 측정할 필요가 없음

if (eatDesert(XY, i, j) == true) {

MaxSize = eatSize;

}

}


}

}


}


}


// 탐색 순서를 고려하여 배치

static int[] rotY = { 1, 1, -1, -1 };

static int[] rotX = { 1, -1, -1, 1 };


private static boolean eatDesert(int XY, int left, int right) {

// XY: 현재좌표, left: 좌로 움직일 수 있는 범위, right: 우로 움직일수 있는 범위

int y = XY / MapSize;

int x = XY % MapSize;


int[] visited = new int[DesertMaxNo+1];


// ↘ 방향 right 번 -> ↙ 방향 left 번 -> ↖ 방향 right 번 -> ↗ 방향 left번

for (int i = 0; i < right; i++) {

y += rotY[0];

x += rotX[0];


if (visited[Map[y][x]]==1) {

return false;

} else {

visited[Map[y][x]] = 1;

}

}


for (int i = 0; i < left; i++) {

y += rotY[1];

x += rotX[1];


if (visited[Map[y][x]]==1) {

return false;

} else {

visited[Map[y][x]] = 1;

}


}


for (int i = 0; i < right; i++) {

y += rotY[2];

x += rotX[2];


if (visited[Map[y][x]]==1) {

return false;

} else {

visited[Map[y][x]] = 1;

}


}


for (int i = 0; i < left; i++) {

y += rotY[3];

x += rotX[3];


if (visited[Map[y][x]]==1) {

return false;

} else {

visited[Map[y][x]] = 1;

}


}


return true;

}


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));

}

}


}

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));

}

}


}

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.StringTokenizer;


class People {

int no;

int cept = -1;

int pair = -1;


public People(int no) {

this.no = no;

}


public void tag(int i) {


if (cept == -1) {

cept = i;

} else if (pair == -1) {

pair = i;

}

}



}


class Factory {


int seatSize;

int[] state;

People[] seat;


ArrayList<Integer> wList;

Queue<People> inQueue;

Queue<People> outQueue;


public Factory(ArrayList<Integer> wList, Queue inQueue, Queue outQueue) {

this.seatSize = wList.size();


this.wList = wList;

this.inQueue = inQueue;

this.outQueue = outQueue;


state = new int[seatSize];

seat = new People[seatSize];

for(int i=0 ; i<seatSize; i++) {

state[i] = wList.get(i);

}

}


public void tick() {


for (int i = 0; i < seatSize; i++) {

if (seat[i]!=null && state[i] != 0) {

state[i]--;

}

}


}


public void comeOut() {


for (int i = 0; i < seatSize; i++) {

if (seat[i]!=null && state[i] == 0) {

outQueue.offer(seat[i]);

state[i] = wList.get(i);

seat[i] = null;

}

}


}


public void comeIn() {


for (int i = 0; i < seatSize; i++) {

if (state[i] == wList.get(i)) {

if (!inQueue.isEmpty()) {

seat[i] = inQueue.poll();

seat[i].tag(i+1);

// Solution.log(seat[i]!=null ?"O":"X");

}

}

}


}


}


class Solution {


static boolean Debug = true;

private static int T;


public static void main(String args[]) throws Exception {


BufferedReader br;

if (Debug) {

// C:\Users\wvimi\Downloads\input (2).txt

File f = new File("C:\\Users\\wvimi\\Downloads", "sample_input (8).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++) {


st = new StringTokenizer(br.readLine());

int ReceptSize = Integer.parseInt(st.nextToken());

int RepairSize = Integer.parseInt(st.nextToken());

int CustomerNum = Integer.parseInt(st.nextToken());

int ReceptUseNo = Integer.parseInt(st.nextToken());

int RepairUseNo = Integer.parseInt(st.nextToken());


// 좌석 마다 걸리는 시간

st = new StringTokenizer(br.readLine());

ArrayList<Integer> cepList = new ArrayList();

for (int i = 0; i < ReceptSize; i++) {

cepList.add(Integer.parseInt(st.nextToken()));

}

// 좌석 마다 걸리는 시간

ArrayList<Integer> piarList = new ArrayList();

st = new StringTokenizer(br.readLine());

for (int i = 0; i < RepairSize; i++) {

piarList.add(Integer.parseInt(st.nextToken()));

}


// 고객 오는 스케줄

st = new StringTokenizer(br.readLine());

ArrayList<Integer> duleList = new ArrayList();

for (int i = 0; i < CustomerNum; i++) {

duleList.add(Integer.parseInt(st.nextToken()));

}


// 로비1(대기), 로비2(대기), 로비3(완료)

Queue<People> Robby1 = new LinkedList();

Queue<People> Robby2 = new LinkedList();

Queue<People> Robby3 = new LinkedList();


Factory cepFactory = new Factory(cepList, Robby1, Robby2);

Factory pairFactory = new Factory(piarList, Robby2, Robby3);


boolean isduleEnd = false;

int timer = -1;

while (true) {

timer++;


// Robby1에 손님 입장

if (!isduleEnd) {

for (int i = 0; i < CustomerNum; i++) {

// 시간이 되면 입장한다.

if (duleList.get(i) == timer) {

Robby1.offer(new People(i+1));

// 마지막 고객까지 나갔다면

if (i == CustomerNum) {

isduleEnd = true;

}

}

}

}


// 시간이 흐른다. (작업량 1감소)

cepFactory.tick();

pairFactory.tick();


// 완료된 사람은 다음 장소로 이동.

cepFactory.comeOut();

pairFactory.comeOut();


// 대기 중인 사람은 들어온다.

cepFactory.comeIn();

pairFactory.comeIn();


if (Robby3.size() == CustomerNum) {

// 모든 고객이 일을 마친다면...

break;

}

}


int Answer = 0;


People person;

while(!Robby3.isEmpty()) {

person = Robby3.poll();

// 지갑을 놓고온 접수, 수리 테이블을 이용한 고객을 추적

if(person.cept == ReceptUseNo && person.pair == RepairUseNo) {

Answer += person.no;

}else {

// Non-target

}

}


System.out.println(String.format("#%d %d", T, Answer > 0 ? Answer : -1));

}


}


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));

}

}


}

+ Recent posts