import java.io.BufferedReader;

import java.io.File;

import java.io.FileReader;

import java.io.InputStreamReader;

import java.util.ArrayList;

import java.util.HashSet;

import java.util.Stack;

import java.util.StringTokenizer;


class Point {

int y, x;


public Point(int y, int x) {

this.y = y;

this.x = x;

}

}


class Process {

int y, x;


public Process(int y, int x) {

this.y = y;

this.x = x;

}


HashSet<Point> moveSet = new HashSet();


public boolean on(int rIndex) {

// 해당 방향으로 전선을 잇는다.


int nextY = y;

int nextX = x;

int endIndex = Solution.MapSize - 1;


while (true) {

nextY += Solution.rotY[rIndex];

nextX += Solution.rotX[rIndex];


if (isRight(nextY, nextX)) {

// 경로기록

moveSet.add(new Point(nextY, nextX));

//경계지점에 도달

if (nextX == 0 || nextY == 0 || nextX == endIndex || nextY == endIndex) {

// 전선연결

for (Point item : moveSet) {

Solution.Visited[item.y][item.x] = 1;

}


return true;

}

} else {

// 경로 삭제

moveSet.clear();

return false;

}

}

}


public boolean isRight(int y, int x) {

if (x < 0 || y < 0 || x >= Solution.MapSize || y >= Solution.MapSize) {

// 배열범위

return false;

} else if (Solution.Visited[y][x] != 0) {

// 해당구획

return false;

}

return true;

}


public void off() {

// 전선을 제거한다.

for (Point item : moveSet) {

Solution.Visited[item.y][item.x] = 0;

}


moveSet.clear();

}


}


class Solution {


static boolean Debug = true;

private static int T;

static int MapSize;


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

private static ArrayList<Process> pList;

private static int processLen;

private static int[] checkMin;


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


BufferedReader br;

if (Debug) {

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

Visited = new int[MapSize][];


// Map 읽기

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

// Map[i] = new int[MapSize];

Visited[i] = new int[MapSize];

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

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


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

// 맵, Visited 초기화

Visited[i][j] = item == 1 ? 2 : item; // 0:빈공간, 1:방문, 2:프로세스


// 프로세스 등록

if (item == 1) {

boolean inner = i != 0 && j != 0 && i != MapSize - 1 && j != MapSize - 1;

if (inner) {

// 관리 프로세스에 등록

pList.add(new Process(i, j));

}

}


}

}


offProcLen = Integer.MAX_VALUE;

processLen = pList.size();

checkMin = new int[13];


// 최대 값을 저장할 배열

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

checkMin[i] = Integer.MAX_VALUE;

}


// 탐색

findPath(0, 0);


// 결과 출력

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

// 성공한 길이를 탐색

if (checkMin[i] != Integer.MAX_VALUE) {

System.out.println(String.format("#%d %d", T, checkMin[i]));

break;

}

// 그 어떤 전선도 없는 경우

if (i == 0) {

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

}

}


}


}


static int offProcLen; // 도달한 0의 개수 (브레이크 조건으로 활용)

static Stack<Integer> debStack = new Stack();


private static void findPath(int index, int bitmask) {


// 끝지점에 도달

if (index == processLen) {


// 0을 몇 번 썼는지 체크

int count_one = countOne(bitmask);

int offLen = processLen - count_one;

if (offProcLen > offLen) {

offProcLen = offLen;

}


// 전선의 길이

int length = 0;

for (Process process : pList) {

length += process.moveSet.size();

}


// 프로세스 개수 별로 최대 개수를 달리한다.

if (checkMin[count_one] > length) {

checkMin[count_one] = length;

}


return;

}


Process item = pList.get(index);


// 프로세스에 전선을 잇는 경우

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

// 연결이 가능한 경우에만 탐색

int nextBitmask = bitmask + (1 << index);


// 최대 끌 수 있는 프로세스를 고려 (1개까지 꺼서 성공했으면, 2개는 허용 못함)

if (index + 1 - countOne(nextBitmask) <= offProcLen)

if (item.on(i)) {

// debStack.add(i + 1);

findPath(index + 1, nextBitmask);

item.off();

// debStack.pop();

}

}


// 프로세스에 전선을 잇지 않는 경우

// debStack.add(0);

findPath(index + 1, bitmask);

// debStack.pop();


}


static void printMap() {


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

String temp = "";

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

temp += Visited[i][j];

}

log(temp);

}


}


private static int countOne(int bitmask) {


int count = 0;

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

if ((bitmask & (1 << i)) != 0) {

count++;

} else {


}

}


return count;

}


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

static int[] rotX = { 0, 1, 0, -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));

}

}


}

'Knowledge > 알고리즘' 카테고리의 다른 글

[스크랩] MD5 (위키백과)  (0) 2018.06.04
백준 3671번: 산업 스파이의 편지  (0) 2017.10.20
백준 14500번: 테트로미노  (0) 2017.10.20
백준 13460번: 째로탈출2  (0) 2017.10.20
백준 12100번: 2048(Easy)  (0) 2017.10.19

import java.io.BufferedReader;

import java.io.File;

import java.io.FileReader;

import java.io.InputStreamReader;

import java.util.HashSet;

import java.util.StringTokenizer;


public class Main {


private static boolean Debug = true;

private static int PrimeCount;

static int[] pocket;

static HashSet<String> primeSet;

private static int NumberLen;

private static int T;


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


BufferedReader br;


if (Debug) {

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

FileReader reader = new FileReader(f);

br = new BufferedReader(reader);

} else {

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

}

StringTokenizer st;


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

for (T = 0; T < TestLen; T++) {


String NumberStr = br.readLine();

NumberLen = NumberStr.length();

pocket = new int[NumberLen];

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

pocket[i] = NumberStr.charAt(i) - '0';

}


// 탐색 리스트 초기화

primeSet = new HashSet();

findPath(0, "");

primeSet.remove("");


PrimeCount = 0;

for (String item : primeSet) {

// 소수라면 PrimeCount++

isPrime(Integer.parseInt(item));

}


// 소수의 개수 출력

System.out.println(PrimeCount);

}


}


// 소수 판별

private static boolean isPrime(int num) {


// 2 ~ 제곱근까지 검색

int end = (int) Math.sqrt(num);

for (int i = 2; i <= end; i++) {

if (num % i == 0) {

return false;

}

}


// 2보다 작으면 안되!

if (num < 2) {

return false;

}


PrimeCount++;

return true;

}


private static void findPath(int check, String input) {

// 중복되는 경우는 제거

if (primeSet.contains(input)) {

return;

} else {

primeSet.add(input);

}


// 0인 비트를 골라 1로 채운뒤, 문자열을 조립한다.

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


int using = 1 << i;


// 시작은 0을 제외한다.

if (check == 0 && pocket[i] == 0) {

continue;

}


if ((check & using) == 0) {

findPath(check + using, input + pocket[i]);

}


}


}


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

import java.util.Map.Entry;

import java.util.StringTokenizer;


class Block {


HashMap<Integer, int[][]> shapeList;

int[][] origin;

int[] flag;

ArrayList<Integer> fList;


// 블록에 해당하는 모양 Data를 만들어줍니다.

public Block(int[][] data, int[] flag) {

this.origin = data;

this.flag = flag;


fList = new ArrayList<>();

for (int item : flag) {

fList.add(item);

}


shapeList = new HashMap<>();

createShape();

// printAllShape();

}


// 회전과 대칭에 따른 데이터(모양) 생성

private void createShape() {


int[][] temp = origin;


// 0번 모양

shapeList.put(0, origin);


// 1~3번 모양(90, 180, 270)

for (int i = 1; i <= 3; i++) {

temp = rotate(temp);

if (fList.contains(i)) {

shapeList.put(i, temp);

}

}


// 4번 모양

int[][] rev = null;

if (fList.contains(4)) {

rev = reverse(origin);

shapeList.put(4, rev);

}


temp = rev;

// 5~7번 모양 rev + (90, 180, 270)

if (fList.contains(5)) {

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

temp = rotate(temp);

shapeList.put(i, temp);

}

}


}


// 디버깅을 위한 출력

public void printAllShape() {


int[][] shape;

int ysize, xsize;

for (Entry<Integer, int[][]> entry : shapeList.entrySet()) {


shape = entry.getValue();

ysize = shape.length;

xsize = shape[0].length;


Main.log("[%d]", entry.getKey());


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

String line = "";

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

line += String.format("%d ", shape[i][j]);

}

Main.log(line);

}

}


}


// 회전 유틸

private int[][] rotate(int[][] data) {

int ysize = data.length;

int xsize = data[0].length;

int end_index = ysize - 1;


int[][] rData = new int[xsize][];

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

rData[i] = new int[ysize];

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

rData[i][j] = data[end_index - j][i];

}

}


return rData;

}


// 대칭 유틸

private int[][] reverse(int[][] data) {

int ysize = data.length;

int xsize = data[0].length;

int end_index = xsize - 1;


int[][] rData = new int[ysize][];

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

rData[i] = new int[xsize];

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

rData[i][j] = data[i][end_index - j];

}

}


return rData;

}


}


public class Main {


private static int MapSize_Y;

private static int MapSize_X;

static int[][] Map;


static private ArrayList<Block> bList;


private static boolean Debug = true;

private static int MaxSum;


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


BufferedReader br;


if (Debug) {

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


// 맵 데이터 입력

Map = new int[MapSize_Y][];

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

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

Map[i] = new int[MapSize_X];

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

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

}

}


// 블록을 담을 리스트

bList = new ArrayList<>();

Block item; // 블록에는 모양 값들이 저장 된다.


// 블록 모양, 필요한 모양 값 (0: 원형, 1~3: 회전, 4: 대칭, 5~7: 대칭 후 회전)

int[][] 네모Shape = { { 1, 1 }, { 1, 1 } };

item = new Block(네모Shape, new int[] { 0 });

bList.add(item);


int[][] 일자Shape = { { 1, 1, 1, 1 } };

item = new Block(일자Shape, new int[] { 0, 1 });

bList.add(item);


int[][] 산Shape = { { 1, 1, 1 }, { 0, 1, 0 } };

item = new Block(산Shape, new int[] { 0, 1, 2, 3 });

bList.add(item);


int[][] 기역Shape = { { 1, 0 }, { 1, 0 }, { 1, 1 } };

item = new Block(기역Shape, new int[] { 0, 1, 2, 3, 4, 5, 6, 7 });

bList.add(item);


int[][] 어긋Shape = { { 1, 0 }, { 1, 1 }, { 0, 1 } };

item = new Block(어긋Shape, new int[] { 0, 1, 2, 3, 4, 5, 6, 7 });

bList.add(item);


// 완전탐색

MaxSum = -1;

dfs();


// 시간 출력

System.out.println(MaxSum);

}


public static void dfs() {


int blockLen = bList.size();

// 모든 블록에 대한 경우

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

Block block = bList.get(i);


// 각 블록에 따른 데이터를 가져온다. (대칭 및 회전이 포함된 데이터)

for (Entry<Integer, int[][]> item : block.shapeList.entrySet()) {

int[][] data = item.getValue();

int ysize = data.length, xsize = data[0].length;


// 탐색범위 지정(드레그)

int endy, endx;

endy = MapSize_Y - ysize;

endx = MapSize_X - xsize;


// 지정된 탐색 범위에서, data에 맞도록 검색

search(endy, endx, data);

}


}


}


// 해당 블록 모양을 가지고, 해당 위치에서 검색을 해봅니다.

public static void search(int endy, int endx, int[][] data) {


// 탐색 사이즈

int yszie = data.length, xsize = data[0].length;

// 탐색 구간은 (0,0) ~ (endy, endx) 드레그

for (int y = 0; y <= endy; y++) {

for (int x = 0; x <= endx; x++) {


// Block 모양에 따른 탐색

int sum = 0;

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

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

if (data[i][j] == 1) { // 탐색

sum += Map[y + i][x + j];

}

}

}


// 최대값 판별

if (MaxSum < sum) {

MaxSum = sum;

}


}

}

// log("합: " + sum);

}


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

1767. [SW Test 샘플문제] 프로세서 연결하기  (0) 2017.10.21
백준 3671번: 산업 스파이의 편지  (0) 2017.10.20
백준 13460번: 째로탈출2  (0) 2017.10.20
백준 12100번: 2048(Easy)  (0) 2017.10.19
백준 3190번: 뱀  (0) 2017.10.19

import java.io.BufferedReader;

import java.io.File;

import java.io.FileReader;

import java.io.InputStreamReader;

import java.util.Stack;

import java.util.StringTokenizer;


class Ball {


int y, x;

static int MapSize_Y;

static int MapSize_X;

static int holeY;

static int holeX;


public Ball(int y, int x) {

this.y = y;

this.x = x;


Main.Map[y][x] = 'X'; // 공의 위치 표기

}


public void move(int rIndex) {


int tempY = y;

int tempX = x;

int moveY = y + Main.rotY[rIndex];

int moveX = x + Main.rotX[rIndex];

// 한 방향으로 직진

while (isRight(moveY, moveX)) {

// 성공좌표를 저장 한다.


y = moveY;

x = moveX;


// 전진

moveY += Main.rotY[rIndex];

moveX += Main.rotX[rIndex];

}


// 공의 위치를 변경한다.

Main.Map[tempY][tempX] = '.';

Main.Map[y][x] = isHoll() ? 'O' : 'X';

}


public void move(int inputY, int inputX) {

Main.Map[this.y][this.x] = isHoll() ? 'O' : '.';

this.y = inputY;

this.x = inputX;

Main.Map[this.y][this.x] = isHoll() ? 'O' : 'X';

}


public boolean isRight(int inputY, int inputX) {


if (inputY < 0 || inputX < 0 || inputY >= MapSize_Y || inputX >= MapSize_X) {

// 배열 밖이라면 No

return false;

} else if (isHoll()) {

// 구멍에 있다면 No

return false;

} else if (Main.Map[inputY][inputX] == 'O') {

// 구멍으로 간다면 Yes

return true;

}


// 빈칸이라면 Yes

return Main.Map[inputY][inputX] == '.';

}


public int getXY() {

return y * MapSize_X + x;

}


public boolean isHoll() {

return Ball.holeX == x && Ball.holeY == y;

}


}


public class Main {


private static boolean Debug = true;


private static final int left = 3, right = 1, up = 0, down = 2;

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

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


private static int MapSize_Y;

private static int MapSize_X;

static char[][] Map;

private static int minFindRed;

static Ball rBall;


private static Ball bBall;


private static int[][] Visited;


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


BufferedReader br;


if (Debug) {

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

Ball.MapSize_Y = MapSize_Y;

Ball.MapSize_X = MapSize_X;


// 맵 생성

Map = new char[MapSize_Y][];

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

Map[i] = new char[MapSize_X];

String input = br.readLine();

char item;

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


// 맵에 기록, Ball 객체 생성

item = input.charAt(j);

switch (item) {

case 'B':

bBall = new Ball(i, j);

Map[i][j] = 'X';

break;

case 'R':

rBall = new Ball(i, j);

Map[i][j] = 'X';

break;

case 'O':

Ball.holeY = i;

Ball.holeX = j;

Map[i][j] = 'O';

break;

default:

Map[i][j] = item;

break;

}

}

}


// 방문배열 생성 [rBall.getXY()][bBall.getXY()]

int vSize = MapSize_X * MapSize_Y;

Visited = new int[vSize][];

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

Visited[i] = new int[vSize];

}


minFindRed = Integer.MAX_VALUE;

// 프레임 체크 (첫 번째 순간은 중복되지 않는다.)

Visited[rBall.getXY()][bBall.getXY()] = 1;


// printMap();

tiltBoard(0);


// 시간 출력

System.out.println(minFindRed == Integer.MAX_VALUE ? -1 : minFindRed);

}


static Stack<Integer> debStack = new Stack();


private static void tiltBoard(int index) {


if (minFindRed <= index) {

// log("탐색불필요 " + debStack);

return;

} else if (bBall.isHoll()) {

// log("[블루볼] " + debStack);

return;

}


// 1.레드볼 여부 && 2. index == 10

if (rBall.isHoll()) { // && !bBall.isHoll() // 위에서 이미 체크

if (minFindRed > index) {

minFindRed = index;

}

// log("[레드볼]" + debStack.toString());

return;

} else if (index == 10) {

// log("[index 10] " + debStack);

return;

}


int redY = rBall.y;

int redX = rBall.x;

int blueY = bBall.y;

int blueX = bBall.x;

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


// 1. 공을 움직인다.

switch (i) {

case left:

if (redX < blueX) {

rBall.move(i);

bBall.move(i);

} else {

bBall.move(i);

rBall.move(i);

}

break;

case right:

if (redX > blueX) {

rBall.move(i);

bBall.move(i);

} else {

bBall.move(i);

rBall.move(i);

}

break;

case up:

if (redY < blueY) {

rBall.move(i);

bBall.move(i);

} else {

bBall.move(i);

rBall.move(i);

}

break;

case down:

if (redY > blueY) {

rBall.move(i);

bBall.move(i);

} else {

bBall.move(i);

rBall.move(i);

}

break;

}


// 2. 가능한 위치로 이동하여 탐색한다. (좌표 정보는 Ball 객체에 담겨있다.)

// 모두 제자리에 있으면, 탐색X

// 실행됬던 프레임이라면, 탐색X

if (rBall.x == redX && rBall.y == redY && bBall.x == blueX && bBall.y == blueY) {

// non-target

} else if (Visited[rBall.getXY()][bBall.getXY()] == 0) {

Visited[rBall.getXY()][bBall.getXY()] = 1;

// debStack.push(i);


// printMap();

tiltBoard(index + 1);


Visited[rBall.getXY()][bBall.getXY()] = 0;

// debStack.pop();

}


// 3. 공을 원위치로 시킨다.

rBall.move(redY, redX);

bBall.move(blueY, blueX);

}


}


// 디버깅용 프린트 맵

private static void printMap() {


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

String temp = "";

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

temp += Map[i][j];

}

if (i == 0) {

temp += "시작";

}

log(temp);

}


}


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

백준 3671번: 산업 스파이의 편지  (0) 2017.10.20
백준 14500번: 테트로미노  (0) 2017.10.20
백준 12100번: 2048(Easy)  (0) 2017.10.19
백준 3190번: 뱀  (0) 2017.10.19
백준 14499번: 주사위 굴리기  (0) 2017.10.19

import java.io.BufferedReader;

import java.io.File;

import java.io.FileReader;

import java.io.InputStreamReader;

import java.util.LinkedList;

import java.util.Queue;

import java.util.StringTokenizer;


public class Main {


private static boolean Debug = true;

private static int MapSize;

private static int[][] OriginMap;

private static int[][] CopyMap;

private static Queue<Integer>[] bQueue;

static int MaxNum = 0;


final static int north = 0, east = 1, south = 2, west = 3;


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


BufferedReader br;


if (Debug) {

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

FileReader reader = new FileReader(f);

br = new BufferedReader(reader);

} else {

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

}

StringTokenizer st;


// 맵 크기, 사과 개수

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

MaxNum = 0;


// 맵 생성

OriginMap = new int[MapSize][];

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

OriginMap[i] = new int[MapSize];

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

int item;

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

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

OriginMap[i][j] = item;

// 합칠 수 없는 경우, 처음 주어진 수가 가장 크다.

if (MaxNum < item) {

MaxNum = item;

}

}

}


// 큐 초기화 (블록을 옮기는 데 사용된다.

bQueue = new LinkedList[MapSize];

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

bQueue[i] = new LinkedList<>();

}


// 00000 ~ 33333

int[] bitmasking = new int[5];

execute(bitmasking, 0);


// 시간 출력

System.out.println(MaxNum);

}


private static void execute(int[] bitmask, int index) {


// 비트마스킹을 조립

if (index <= 4) {

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

bitmask[index] = i;

execute(bitmask, index + 1);

}

return;

}


// 맵초기화

initMap();


// 실행

int rIndex;

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

rIndex = bitmask[i];

tiltMap(rIndex);

}


}


private static void initMap() {


// Merge를 위한 지도 초기화

CopyMap = new int[MapSize][];

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

CopyMap[i] = new int[MapSize];

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


int num = OriginMap[i][j];

if (num != 0) { // 0은 빈공간

CopyMap[i][j] = num;

} else {

// non-target

}

}

}


}


private static void tiltMap(int rIndex) {

// log("tiltMap(%d)", rIndex);


// 정방향|역방향

// 행기준|열기준

boolean good = (rIndex == west || rIndex == north);

boolean isRow = (rIndex == west || rIndex == east);

// 방향에 따른 병합 및 매칭

int j_start = (good ? 0 : MapSize - 1);

int j_end = (good ? MapSize : -1);

int j_add = (good ? 1 : -1);


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

// 1. 큐에 대입

int j = j_start;

while (j != j_end) {


// 행기준 열기준에 따라 값을 큐에 넣는다. 

int item = isRow ? CopyMap[i][j] : CopyMap[j][i];

if (item != 0) {

bQueue[i].add(item);

// 값을 옮기면, 해당 자리는 빈공간으로 체크

if (isRow) {

CopyMap[i][j] = 0;

} else {

CopyMap[j][i] = 0;

}

}


j += j_add;

}


// 2. 머지

bQueue[i] = mergeBlock(bQueue[i]);


// 3. 맵에 매칭

j = j_start;

while (j != j_end) {

if (!bQueue[i].isEmpty()) {


if (isRow) {

CopyMap[i][j] = bQueue[i].poll();

// log("큐 방출 [%d][%d] = %d", i, j, CopyMap[i][j].num);

} else {

CopyMap[j][i] = bQueue[i].poll();

// log("큐 대입 [%d][%d] = %d", j, i, CopyMap[j][i].num);

}


} else {

break;

}

j += j_add;

}


}


}


static Queue<Integer> rQue;


private static Queue<Integer> mergeBlock(Queue<Integer> que) {


// 반환을 위한 큐

rQue = new LinkedList<>();


// 합치고

int item1 = 0, item2 = 0;

while (true) {


// 합칠 대상1 픽업

if (item1 == 0) {

if (!que.isEmpty()) {

item1 = que.poll();

} else {

// 큐가 비었으므로

break;

}

}


// 합칠 대상2 픽업

if (item2 == 0) {

if (!que.isEmpty()) {

item2 = que.poll();

} else {

// 비교대상이 없으므로

rQue.add(item1);

break;

}

}


// item1과 item2를 합친다.

if (item1 == item2) {


int mergeNum = item1 * 2;

rQue.add(mergeNum);


// 최고값 측정

if (MaxNum < mergeNum) {

MaxNum = mergeNum;

}

item1 = 0;

item2 = 0;

} else { // 합칠수 없는 경우, 이전 비교대상은 rQue에 넣는다.


rQue.add(item1);

item1 = item2; // 다음비교 대상이 첫번 째가 된다.

item2 = 0;

}


}


return rQue;

}


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

백준 14500번: 테트로미노  (0) 2017.10.20
백준 13460번: 째로탈출2  (0) 2017.10.20
백준 3190번: 뱀  (0) 2017.10.19
백준 14499번: 주사위 굴리기  (0) 2017.10.19
백준 14502번: 연구소  (0) 2017.10.17

import java.io.BufferedReader;

import java.io.InputStreamReader;

import java.util.Hashtable;

import java.util.LinkedList;

import java.util.Queue;

import java.util.StringTokenizer;


class Snake {

Queue<Integer> body = new LinkedList<>();


// 해당 위치로 움직인다.

void move(int where, boolean hasApple) {

if (hasApple) {

body.add(where);

} else {

body.poll();

body.add(where);

}

}


// 자기 자신에 충돌하는지 체크한다.

boolean isSelf(int where) {

return body.contains(where);

}

}


public class Main {


private static boolean Debug = false;

private static int MapSize;

private static int[][] Map;

private static Hashtable<Integer, Character> comMap;

private static Snake snake = new Snake();


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


BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

StringTokenizer st;


// 맵 크기, 사과 개수

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

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


// 맵 생성

Map = new int[MapSize][];

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

Map[i] = new int[MapSize];

}


// 사과 위치 배정

int y, x;

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

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

y = Integer.parseInt(st.nextToken()) - 1;

x = Integer.parseInt(st.nextToken()) - 1;

Map[y][x] = 1;

}


// 커맨드 읽기

comMap = new Hashtable();

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

int time;

char direct;

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

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

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

direct = st.nextToken().charAt(0);

comMap.put(time, direct);

}


// 위치 초기화, 시간 초기화

y = x = 0;

rIndex = 1;

timer = 0;


// 뱀이 움직인다.

snake.move(0, false);

findPath();


// 시간 출력

System.out.println(timer);

}


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

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


static int y, x;

static int rIndex;

static int timer;


private static void findPath() {


// 해당 시간에 방향 전환이 발생하는가?

if (comMap.containsKey(timer)) {

char direct = comMap.get(timer);


// 왼쪽 회전 =>  rIndex--;  // 오른쪽 회전 => rIndex++;

if (direct == 'L') {

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

} else {

rIndex = rIndex == 3 ? 0 : rIndex + 1;

}

comMap.remove(timer);

}


// 움직임이 시작되는 순간

timer++;


// 움직이려는 방향이 맞다면 움직인다.

if (isVaild(rIndex)) {


y += rotY[rIndex];

x += rotX[rIndex];


int where = y * MapSize + x;

// 자신의 몸에 충돌하는가?

if (snake.isSelf(where)) {

return;

}


// 사과가 있다면

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

Map[y][x] = 0;

snake.move(where, true);

} else { // 사과가 없다면

snake.move(where, false);

}


findPath();

} else {

// 움직이는 방향이 맵 밖인 경우, 이탈한다.

return;

}


}


// 해당 방향이 맵의 범위를 초과하는지를 판단한다.

private static boolean isVaild(int index) {


switch (index) {

case 0:

return y - 1 >= 0;

case 2:

return y + 1 < MapSize;

case 1:

return x + 1 < MapSize;

case 3:

return x - 1 >= 0;

}


return false;

}


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

백준 13460번: 째로탈출2  (0) 2017.10.20
백준 12100번: 2048(Easy)  (0) 2017.10.19
백준 14499번: 주사위 굴리기  (0) 2017.10.19
백준 14502번: 연구소  (0) 2017.10.17
백준 14501번: 퇴사  (0) 2017.10.17

import java.io.BufferedReader;

import java.io.InputStreamReader;

import java.util.StringTokenizer;


class Dice {

private int[] face;


static final int Left = 1, Right = 2;

static final int Up = 3, Down = 4;


int top, bottom;

int north, south;

int west, east;


// 전개도를 펼쳤을 때, 가운데를 top이라 생각하고, 각각의 면에 index를 메김

public Dice() {

top = 1;

bottom = 6;

north = 2;

south = 5;

west = 4;

east = 3;


face = new int[7];

}


// 주사위 디버깅

private void printDice() {

Main.log("%2d%2d%2d", 0, north, 0);

Main.log("%2d%2d%2d", west, top, east);

Main.log("%2d%2d%2d", 0, south, 0);

Main.log("%2d%2d%2d", 0, bottom, 0);

}


// 주사위를 해당 방향에 굴린 후, 바닥면을 주사위로 옮긴다.

public int move(int direct, int num) {


// 주사위를 굴리면 전개도에서 4면의 변화가 생김

int temp;

switch (direct) {

case Up:

temp = north;

north = top;

top = south;

south = bottom;

bottom = temp;

break;

case Down:

temp = bottom;

bottom = south;

south = top;

top = north;

north = temp;

break;

case Left:

temp = west;

west = top;

top = east;

east = bottom;

bottom = temp;

break;

case Right:

temp = east;

east = top;

top = west;

west = bottom;

bottom = temp;

break;

}


// 윗면 출력

System.out.println(face[top]);

// printDice();


// 주사위 면 복사

int result;

result = face[bottom];

if (num != 0) {

face[bottom] = num;

}


return result;

}


}


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[] Command;

private static Dice Dice;

private static int startY;

private static int startX;


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


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


// 주사위 시작 위치

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

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

Command = new int[Integer.parseInt(st.nextToken())];


// 맵 읽기

Map = new int[MapSize_Y][];

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

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

Map[i] = new int[MapSize_X];

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

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

}

}


// 커맨드 읽기

int clen = Command.length;

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

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

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

}


Dice = new Dice();


MoveDice();

// System.out.println(MaxSafeCount);

}


// 1~4 동서북남

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

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


private static void MoveDice() {


int clen = Command.length;

int y = startY;

int x = startX;


int moveY, moveX;


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

int direct = Command[i];

moveY = y + rotY[direct];

moveX = x + rotX[direct];


if (!isRight(moveY, moveX)) {

continue;

}


// 바닥면의 경우

int mapValue = Map[moveY][moveX];

if (mapValue != 0) {

// 바닥에 0이 아닐때, 숫자는 주사위로 옮겨간다.

Dice.move(direct, mapValue);

Map[moveY][moveX] = 0;

} else {

// 바닥이 0이라면 , 숫자는 맵으로 옮겨간다.

int num = Dice.move(direct, mapValue);

Map[moveY][moveX] = num;

}


y = moveY;

x = moveX;

}

}


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


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

return false;

} else {

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

}

}


}



'Knowledge > 알고리즘' 카테고리의 다른 글

백준 12100번: 2048(Easy)  (0) 2017.10.19
백준 3190번: 뱀  (0) 2017.10.19
백준 14502번: 연구소  (0) 2017.10.17
백준 14501번: 퇴사  (0) 2017.10.17
백준 13458번: 시험 감독  (0) 2017.10.17

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

}

}


}




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