백준 [13460] 구슬탈출2
문제보기
풀이
- DFS
- 같은 열이나 행에 있을땐 어떤 구슬이 앞쪽에 위치하는지가 중요하므로 체크하고 먼저 굴려본다. 다른 행과 열일때는 어떤 구슬이 먼저 굴러가도 상관없으므로 항상 누가 앞에있는지 체크해도 무관
소스코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
static int N, M, ans;
static char[][] map;
static int[][] memo; // R,B
static int[] dx = { -1, 1, 0, 0 };
static int[] dy = { 0, 0, -1, 1 };
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
ans = 987654321;
map = new char[N][M];
memo = new int[2][2];
for (int i = 0; i < N; i++) {
String str = br.readLine();
for (int j = 0; j < M; j++) {
map[i][j] = str.charAt(j);
if (map[i][j] == 'R') {
memo[0][0] = i;
memo[0][1] = j;
map[i][j] = '.';
} else if (map[i][j] == 'B') {
memo[1][0] = i;
memo[1][1] = j;
map[i][j] = '.';
}
}
}
dfs(memo[0][0], memo[0][1], memo[1][0], memo[1][1], 0);
if (ans == 987654321)
ans = -1;
System.out.println(ans);
}
public static void dfs(int rx, int ry, int bx, int by, int cnt) {
if (cnt >= 10 || cnt >= ans) {
return;
}
for (int k = 0; k < 4; k++) {
boolean flag = false;// blue가 먼저 시작해야하면 true
int redX = rx + dx[k];
int redY = ry + dy[k];
int blueX = bx + dx[k];
int blueY = by + dy[k];
if (map[redX][redY] == '#' && map[blueX][blueY] == '#')
continue;
if (k == 0) { // 상
if (ry == by) {
if (rx > bx) {
flag = true;
}
}
} else if (k == 1) { // 하
if (ry == by) {
if (rx < bx) {
flag = true;
}
}
} else if (k == 2) { // 좌
if (rx == bx) {
if (ry > by) {
flag = true;
}
}
} else if (k == 3) { // 우
if (rx == bx) {
if (ry < by) {
flag = true;
}
}
}
boolean isRed = false;
boolean isBlue = false;
if (!flag) { // 빨간공이 먼저 시작
isRed = go(rx, ry, k, 0, 0);
isBlue = go(bx, by, k, 1, 1);
} else {
isBlue = go(bx, by, k, 1, 0);
isRed = go(rx, ry, k, 0, 1);
}
if (isBlue) {
continue;
}
if (isRed) {
ans = Math.min(ans, cnt + 1);
continue;
}
dfs(memo[0][0], memo[0][1], memo[1][0], memo[1][1], cnt + 1);
memo[0][0] = rx;
memo[0][1] = ry;
memo[1][0] = bx;
memo[1][1] = by;
}
}
public static boolean go(int x, int y, int dir, int rb, int order) {
boolean result = false; // 구멍 만남 유무
while (true) {
int r = x + dx[dir];
int c = y + dy[dir];
if (map[r][c] == 'O') {
result = true;
x = r;
y = c;
break;
} else if (map[r][c] == '#') {
break;
}
if (order == 1) {
int idx = 0;
if (rb == 0)
idx = 1;
if (memo[idx][0] == r && memo[idx][1] == c) {
break;
}
}
x = r;
y = c;
}
if (rb == 0) { // 빨간공이라면
memo[0][0] = x;
memo[0][1] = y;
} else {
memo[1][0] = x;
memo[1][1] = y;
}
return result;
}
}