백준 13460번: 째로탈출2

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

}

}

}