백준 알고리즘 - 구슬탈출2
이 문제의 핵심은 어떤 구슬을 먼저 움직여 줄 지인 것 같다.
처음에 놓여진 빨간 구슬과 파란 구슬의 좌표값을 이용해서 우선순위 정해주기
#. . . RB.# 의 경우 왼쪽으로 굴리면 R부터 움직이고 B는 다음에 움직이고,
오른쪽으로 굴리면 B부터 굴리고 R을 다음에 굴린다.
구슬 이동 로직은 재귀를 이용해서 #을 만나거나 O 구멍을 만날 때 까지 계속 호출했다.
이 문제도 결국 최대 10번이다.
4의 10제곱의 경우의 수만 고려하면 된다.
1024 * 1024 는 100만이 조금 넘는다.
100만가지의 경우의 수를 검색해서 구슬이 탈출가능한 지
가능 하다면 최소 몇번만에 빠져가는지 구하면 된다.
하지만 100만가지를 다 검사하니 시간초과가 났다.
그래서 의미없는 움직임을 제외 시켜주니 통과됬다.
1. 같은 방향으로 연속해서 움직이는 경우
2. 왔던 방향으로 움직이는 경우
2가지만 제외해줘도 검사하는 경우의 수가 현저히 줄어든다.
import java.util.HashSet;
import java.util.Iterator;
import java.util.Scanner;
public class Main {
static class InObject {
int y;
int x;
int originY;
int originX;
String type;
}
private static HashSet<Integer> results = new HashSet<>();
public static void main(String[] args) {
InObject red = new InObject();
InObject blue = new InObject();
Scanner scn = new Scanner(System.in);
int n = scn.nextInt();
int m = scn.nextInt();
String[][] ground = new String[n][m];
for (int i = 0; i < n; i++) {
String[] temp = scn.next().split("");
for (int j = 0; j < m; j++) {
if (temp[j].equals("R")) {
red.y = i;
red.x = j;
red.originY = i;
red.originX = j;
red.type = "R";
} else if (temp[j].equals("B")) {
blue.y = i;
blue.x = j;
blue.originY = i;
blue.originX = j;
blue.type = "B";
}
ground[i][j] = temp[j];
}
}
scn.close();
int[] directions = new int[10];
for (int i = 0; i < 4; i++) {
DFS(0, i, ground, red, blue, directions);
}
if (results.size() == 1) {
System.out.println(-1);
} else {
int minValue = 11;
Iterator<Integer> iterator = results.iterator();
while (iterator.hasNext()) {
int temp = iterator.next();
if (temp != -1 && minValue > temp)
minValue = temp;
}
System.out.println(minValue);
}
}
private static void DFS(int depth, int direction, String[][] ground, InObject red, InObject blue, int[] directions) {
directions[depth] = direction;
if (depth == 9) {
for (int i = 0; i < directions.length; i++) {
moveBeads(directions[i], ground, red, blue);
if (checkBeads(red) && !checkBeads(blue)) {
resetEvery(red, blue, ground, true, i+1);
return;
} else if (checkBeads(blue)) {
resetEvery(red, blue, ground, false, i+1);
return;
}
}
resetEvery(red, blue, ground, false, 0);
return;
}
for (int i = 0; i < 4; i++) {
if (directions[depth] == i)
continue;
if (Math.abs(directions[depth] - i) == 2)
continue;
DFS(depth + 1, i, ground, red, blue, directions);
}
}
private static void resetEvery(InObject red, InObject blue, String[][] ground, boolean tf, int cnt) {
if (tf) {
results.add(cnt);
} else {
results.add(-1);
}
resetBeads(red, ground);
resetBeads(blue, ground);
}
private static void resetBeads(InObject bead, String[][] ground) {
if (bead.y == 0 && bead.x == 0) {
ground[bead.y][bead.x] = "#";
} else {
ground[bead.y][bead.x] = ".";
}
bead.y = bead.originY;
bead.x = bead.originX;
ground[bead.y][bead.x] = bead.type;
}
private static boolean checkBeads(InObject bead) {
boolean isFall = false;
if (bead.y == 0 && bead.x == 0)
isFall = true;
return isFall;
}
private static void moveBeads(int direction, String[][] ground, InObject red, InObject blue) {
switch (direction) {
case 0://up
if (red.y - blue.y < 0) {
moveBeadUp(ground, red);
moveBeadUp(ground, blue);
} else {
moveBeadUp(ground, blue);
moveBeadUp(ground, red);
}
break;
case 1://right
if (red.x - blue.x < 0) {
moveBeadRight(ground, blue);
moveBeadRight(ground, red);
} else {
moveBeadRight(ground, red);
moveBeadRight(ground, blue);
}
break;
case 2://down
if (red.y - blue.y > 0) {
moveBeadDown(ground, red);
moveBeadDown(ground, blue);
} else {
moveBeadDown(ground, blue);
moveBeadDown(ground, red);
}
break;
case 3://left
if (red.x - blue.x < 0) {
moveBeadLeft(ground, red);
moveBeadLeft(ground, blue);
} else {
moveBeadLeft(ground, blue);
moveBeadLeft(ground, red);
}
break;
}
}
private static void moveBeadDown(String[][] ground, InObject bead) {
if (ground[bead.y + 1][bead.x].equals(".")) {
ground[bead.y][bead.x] = ".";
ground[bead.y + 1][bead.x] = bead.type;
bead.y += 1;
moveBeadDown(ground, bead);
} else if (ground[bead.y + 1][bead.x].equals("#")) {
return;
} else if (ground[bead.y + 1][bead.x].equals("O")) {
fallIntoHole(ground, bead);
return;
}
}
private static void moveBeadUp(String[][] ground, InObject bead) {
if (ground[bead.y - 1][bead.x].equals(".")) {
ground[bead.y][bead.x] = ".";
ground[bead.y - 1][bead.x] = bead.type;
bead.y -= 1;
moveBeadUp(ground, bead);
} else if (ground[bead.y - 1][bead.x].equals("#")) {
return;
} else if (ground[bead.y - 1][bead.x].equals("O")) {
fallIntoHole(ground, bead);
return;
}
}
private static void moveBeadRight(String[][] ground, InObject bead) {
if (ground[bead.y][bead.x + 1].equals(".")) {
ground[bead.y][bead.x] = ".";
ground[bead.y][bead.x + 1] = bead.type;
bead.x += 1;
moveBeadRight(ground, bead);
} else if (ground[bead.y][bead.x + 1].equals("#")) {
return;
} else if (ground[bead.y][bead.x + 1].equals("O")) {
fallIntoHole(ground, bead);
return;
}
}
private static void moveBeadLeft(String[][] ground, InObject bead) {
if (ground[bead.y][bead.x - 1].equals(".")) {
ground[bead.y][bead.x] = ".";
ground[bead.y][bead.x - 1] = bead.type;
bead.x -= 1;
moveBeadLeft(ground, bead);
} else if (ground[bead.y][bead.x - 1].equals("#")) {
return;
} else if (ground[bead.y][bead.x - 1].equals("O")) {
fallIntoHole(ground, bead);
return;
}
}
private static void fallIntoHole(String[][] ground, InObject bead) {
ground[bead.y][bead.x] = ".";
bead.x = 0;
bead.y = 0;
}
}
처음에 놓여진 빨간 구슬과 파란 구슬의 좌표값을 이용해서 우선순위 정해주기
#. . . RB.# 의 경우 왼쪽으로 굴리면 R부터 움직이고 B는 다음에 움직이고,
오른쪽으로 굴리면 B부터 굴리고 R을 다음에 굴린다.
구슬 이동 로직은 재귀를 이용해서 #을 만나거나 O 구멍을 만날 때 까지 계속 호출했다.
이 문제도 결국 최대 10번이다.
4의 10제곱의 경우의 수만 고려하면 된다.
1024 * 1024 는 100만이 조금 넘는다.
100만가지의 경우의 수를 검색해서 구슬이 탈출가능한 지
가능 하다면 최소 몇번만에 빠져가는지 구하면 된다.
하지만 100만가지를 다 검사하니 시간초과가 났다.
그래서 의미없는 움직임을 제외 시켜주니 통과됬다.
1. 같은 방향으로 연속해서 움직이는 경우
2. 왔던 방향으로 움직이는 경우
2가지만 제외해줘도 검사하는 경우의 수가 현저히 줄어든다.
import java.util.HashSet;
import java.util.Iterator;
import java.util.Scanner;
public class Main {
static class InObject {
int y;
int x;
int originY;
int originX;
String type;
}
private static HashSet<Integer> results = new HashSet<>();
public static void main(String[] args) {
InObject red = new InObject();
InObject blue = new InObject();
Scanner scn = new Scanner(System.in);
int n = scn.nextInt();
int m = scn.nextInt();
String[][] ground = new String[n][m];
for (int i = 0; i < n; i++) {
String[] temp = scn.next().split("");
for (int j = 0; j < m; j++) {
if (temp[j].equals("R")) {
red.y = i;
red.x = j;
red.originY = i;
red.originX = j;
red.type = "R";
} else if (temp[j].equals("B")) {
blue.y = i;
blue.x = j;
blue.originY = i;
blue.originX = j;
blue.type = "B";
}
ground[i][j] = temp[j];
}
}
scn.close();
int[] directions = new int[10];
for (int i = 0; i < 4; i++) {
DFS(0, i, ground, red, blue, directions);
}
if (results.size() == 1) {
System.out.println(-1);
} else {
int minValue = 11;
Iterator<Integer> iterator = results.iterator();
while (iterator.hasNext()) {
int temp = iterator.next();
if (temp != -1 && minValue > temp)
minValue = temp;
}
System.out.println(minValue);
}
}
private static void DFS(int depth, int direction, String[][] ground, InObject red, InObject blue, int[] directions) {
directions[depth] = direction;
if (depth == 9) {
for (int i = 0; i < directions.length; i++) {
moveBeads(directions[i], ground, red, blue);
if (checkBeads(red) && !checkBeads(blue)) {
resetEvery(red, blue, ground, true, i+1);
return;
} else if (checkBeads(blue)) {
resetEvery(red, blue, ground, false, i+1);
return;
}
}
resetEvery(red, blue, ground, false, 0);
return;
}
for (int i = 0; i < 4; i++) {
if (directions[depth] == i)
continue;
if (Math.abs(directions[depth] - i) == 2)
continue;
DFS(depth + 1, i, ground, red, blue, directions);
}
}
private static void resetEvery(InObject red, InObject blue, String[][] ground, boolean tf, int cnt) {
if (tf) {
results.add(cnt);
} else {
results.add(-1);
}
resetBeads(red, ground);
resetBeads(blue, ground);
}
private static void resetBeads(InObject bead, String[][] ground) {
if (bead.y == 0 && bead.x == 0) {
ground[bead.y][bead.x] = "#";
} else {
ground[bead.y][bead.x] = ".";
}
bead.y = bead.originY;
bead.x = bead.originX;
ground[bead.y][bead.x] = bead.type;
}
private static boolean checkBeads(InObject bead) {
boolean isFall = false;
if (bead.y == 0 && bead.x == 0)
isFall = true;
return isFall;
}
private static void moveBeads(int direction, String[][] ground, InObject red, InObject blue) {
switch (direction) {
case 0://up
if (red.y - blue.y < 0) {
moveBeadUp(ground, red);
moveBeadUp(ground, blue);
} else {
moveBeadUp(ground, blue);
moveBeadUp(ground, red);
}
break;
case 1://right
if (red.x - blue.x < 0) {
moveBeadRight(ground, blue);
moveBeadRight(ground, red);
} else {
moveBeadRight(ground, red);
moveBeadRight(ground, blue);
}
break;
case 2://down
if (red.y - blue.y > 0) {
moveBeadDown(ground, red);
moveBeadDown(ground, blue);
} else {
moveBeadDown(ground, blue);
moveBeadDown(ground, red);
}
break;
case 3://left
if (red.x - blue.x < 0) {
moveBeadLeft(ground, red);
moveBeadLeft(ground, blue);
} else {
moveBeadLeft(ground, blue);
moveBeadLeft(ground, red);
}
break;
}
}
private static void moveBeadDown(String[][] ground, InObject bead) {
if (ground[bead.y + 1][bead.x].equals(".")) {
ground[bead.y][bead.x] = ".";
ground[bead.y + 1][bead.x] = bead.type;
bead.y += 1;
moveBeadDown(ground, bead);
} else if (ground[bead.y + 1][bead.x].equals("#")) {
return;
} else if (ground[bead.y + 1][bead.x].equals("O")) {
fallIntoHole(ground, bead);
return;
}
}
private static void moveBeadUp(String[][] ground, InObject bead) {
if (ground[bead.y - 1][bead.x].equals(".")) {
ground[bead.y][bead.x] = ".";
ground[bead.y - 1][bead.x] = bead.type;
bead.y -= 1;
moveBeadUp(ground, bead);
} else if (ground[bead.y - 1][bead.x].equals("#")) {
return;
} else if (ground[bead.y - 1][bead.x].equals("O")) {
fallIntoHole(ground, bead);
return;
}
}
private static void moveBeadRight(String[][] ground, InObject bead) {
if (ground[bead.y][bead.x + 1].equals(".")) {
ground[bead.y][bead.x] = ".";
ground[bead.y][bead.x + 1] = bead.type;
bead.x += 1;
moveBeadRight(ground, bead);
} else if (ground[bead.y][bead.x + 1].equals("#")) {
return;
} else if (ground[bead.y][bead.x + 1].equals("O")) {
fallIntoHole(ground, bead);
return;
}
}
private static void moveBeadLeft(String[][] ground, InObject bead) {
if (ground[bead.y][bead.x - 1].equals(".")) {
ground[bead.y][bead.x] = ".";
ground[bead.y][bead.x - 1] = bead.type;
bead.x -= 1;
moveBeadLeft(ground, bead);
} else if (ground[bead.y][bead.x - 1].equals("#")) {
return;
} else if (ground[bead.y][bead.x - 1].equals("O")) {
fallIntoHole(ground, bead);
return;
}
}
private static void fallIntoHole(String[][] ground, InObject bead) {
ground[bead.y][bead.x] = ".";
bead.x = 0;
bead.y = 0;
}
}
댓글
댓글 쓰기