빨간 구슬만 구멍에 넣어야 함
파란 구슬이 빠지면 안됨
두 구슬이 같은 칸에 있을 수 없음
기존 코드
import java.io.*;
import java.util.*;
public class Main {
static int N;
static int M;
static char[][] map;
static boolean[][][][] visited;
static int gr;
static int gc;
static ArrayList<Integer> cnts;
public static void main(String[] args) throws IOException {
BufferedReader buff = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(buff.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
map = new char[N][M];
cnts = new ArrayList<>();
visited = new boolean[N][M][N][M];
int rr = 0, rc = 0, br = 0, bc = 0;
for (int i = 0; i < N; i++) {
String temp = buff.readLine();
map[i] = temp.toCharArray();
for (int j = 0; j < M; j++) {
if (map[i][j] == 'R') {
rr = i;
rc = j;
} else if (map[i][j] == 'B') {
br = i;
bc = j;
} else if (map[i][j] == 'O') {
gr = i;
gc = j;
}
}
}
roll(rr, rc, br, bc, 0);
if (cnts.isEmpty()) {
System.out.println(-1);
return;
}
cnts.sort(null);
System.out.println(cnts.get(0));
}
static void roll(int r, int c, int br, int bc, int cnt) {
Queue<int[]> q = new LinkedList<>();
int[] s = { r, c, br, bc, cnt };
q.offer(s);
while (!q.isEmpty()) {
int[] current = q.poll();
visited[current[0]][current[1]][current[2]][current[3]] = true;
if (current[4] > 9)
return;
int nr = current[0];
int nbr = current[2];
boolean add = true;
boolean roll = true;
boolean bflag = false;
boolean rflag = false;
while (roll && nr < N && nbr < N && current[1] < M && current[1] >= 0 && current[3] < M
&& current[3] >= 0) {
nr++;
nbr++;
if (map[nr][current[1]] == 'O') {
rflag = true;
}
if (map[nbr][current[3]] == 'O') {
bflag = true;
}
if (map[nr][current[1]] == '#') {
nr--;
if ((nr == nbr && current[1] == current[3]) || map[nbr][current[3]] == '#') {
nbr--;
roll = false;
}
}
if (map[nbr][current[3]] == '#') {
nbr--;
if ((nr == nbr && current[1] == current[3]) || map[nr][current[1]] == '#') {
nr--;
roll = false;
}
}
if (nr == current[0] && nbr == current[2])
add = false;
}
if (add && !visited[nr][current[1]][nbr][current[3]]) {
if (!bflag && rflag) {
cnts.add(current[4] + 1);
} else if (!bflag && !rflag)
q.offer(new int[] { nr, current[1], nbr, current[3], current[4] + 1 });
}
nr = current[0];
nbr = current[2];
bflag = false;
rflag = false;
add = true;
roll = true;
while (roll && nr >= 0 && nr < N && nbr < N && nbr >= 0 && current[1] < M && current[1] >= 0
&& current[3] < M && current[3] >= 0) {
nr--;
nbr--;
if (map[nr][current[1]] == 'O') {
rflag = true;
}
if (map[nbr][current[3]] == 'O') {
bflag = true;
}
if (map[nr][current[1]] == '#') {
nr++;
if ((nr == nbr && current[1] == current[3]) || map[nbr][current[3]] == '#') {
nbr++;
roll = false;
}
}
if (map[nbr][current[3]] == '#') {
nbr++;
if ((nr == nbr && current[1] == current[3]) || map[nr][current[1]] == '#') {
nr++;
roll = false;
}
}
if (nr == current[0] && nbr == current[2])
add = false;
}
if (add && !visited[nr][current[1]][nbr][current[3]]) {
if (!bflag && rflag) {
cnts.add(current[4] + 1);
} else if (!bflag && !rflag)
q.offer(new int[] { nr, current[1], nbr, current[3], current[4] + 1 });
}
int nc = current[1];
int nbc = current[3];
add = true;
roll = true;
rflag=false;
bflag = false;
while (roll && nc < M && nbc < M && current[0] < N && current[0] >= 0 && current[2] < N
&& current[2] >= 0) {
nc++;
nbc++;
if (map[current[0]][nc] == 'O') {
cnts.add(current[4] + 1);
return;
}
if (map[current[2]][nbc] == 'O') {
add = false;
break;
}
if (map[current[0]][nc] == '#') {
nc--;
if ((nc == nbc && current[0] == current[2]) || map[current[2]][nbc] == '#') {
nbc--;
roll = false;
}
}
if (map[current[2]][nbc] == '#') {
nbc--;
if ((nc == nbc && current[0] == current[2]) || map[current[0]][nc] == '#') {
nc--;
roll = false;
}
}
if (nc == current[1] && nbc == current[3])
add = false;
}
if (add && !visited[current[0]][nc][current[2]][nbc]) {
if (!bflag && rflag) {
cnts.add(current[4] + 1);
} else if (!bflag && !rflag)
q.offer(new int[] { current[0], nc, current[2], nbc, current[4] + 1 });
}
nc = current[1];
nbc = current[3];
add = true;
roll = true;
bflag = false;
rflag = false;
while (roll && nc >= 0 && nbc >= 0 && current[0] < N && current[0] >= 0 && current[2] < N
&& current[2] >= 0) {
nc--;
nbc--;
if (map[current[0]][nc] == 'O') {
rflag = true;
}
if (map[current[2]][nbc] == 'O') {
bflag = true;
}
if (map[current[0]][nc] == '#') {
nc++;
if ((nc == nbc && current[0] == current[2]) || map[current[2]][nbc] == '#') {
nbc++;
roll = false;
}
}
if (map[current[2]][nbc] == '#') {
nbc++;
if ((nc == nbc && current[0] == current[2]) || map[current[0]][nc] == '#') {
nc++;
roll = false;
}
}
if (nc == current[1] && nbc == current[3])
add = false;
}
if (add && !visited[current[0]][nc][current[2]][nbc]) {
if (!bflag && rflag) {
cnts.add(current[4] + 1);
} else if (!bflag && !rflag)
q.offer(new int[] { current[0], nc, current[2], nbc, current[4] + 1 });
}
}
}
}✨ 리팩토링 핵심 요점
- 중복 제거: 상하좌우로 구슬을 굴리는 코드가 거의 동일하게 반복되고 있음.
- 가독성 향상: 조건문과 반복문 간결화
1. moveBead() 함수로 구슬 이동 로직 추상화
static int[] moveBead(int r, int c, int dr, int dc)- 구슬 하나를 특정 방향으로 굴려서 멈출 때까지 이동
- 이동 도중 구멍에 빠질 수도 있으므로, 이동 거리도 함께 반환
2. 구슬 충돌 처리 (겹쳤을 때 먼저 움직인 구슬을 앞으로)
if (red[0] == blue[0] && red[1] == blue[1]) {
if (red[2] > blue[2]) {
red[0] -= dx[d]; red[1] -= dy[d];
} else {
blue[0] -= dx[d]; blue[1] -= dy[d];
}
}- 두 구슬이 같은 위치로 도착한 경우 → 움직인 거리가 더 큰 구슬을 뒤로 한 칸 이동
- 빨간 구슬과 파란 구슬은 동시에 같은 칸에 있을 수 없기 때문
import java.io.*;
import java.util.*;
public class Main {
static int N, M;
static char[][] map;
static boolean[][][][] visited;
static int holeR, holeC;
static final int[] dx = {-1, 1, 0, 0}; // 상 하 좌 우
static final int[] dy = {0, 0, -1, 1};
public static void main(String[] args) throws IOException {
BufferedReader buff = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(buff.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
map = new char[N][M];
visited = new boolean[N][M][N][M];
int rr = 0, rc = 0, br = 0, bc = 0;
for (int i = 0; i < N; i++) {
String temp = buff.readLine();
for (int j = 0; j < M; j++) {
map[i][j] = temp.charAt(j);
if (map[i][j] == 'R') {
rr = i;
rc = j;
} else if (map[i][j] == 'B') {
br = i;
bc = j;
} else if (map[i][j] == 'O') {
holeR = i;
holeC = j;
}
}
}
int result = bfs(rr, rc, br, bc);
System.out.println(result);
}
static int bfs(int rr, int rc, int br, int bc) {
Queue<int[]> q = new LinkedList<>();
q.offer(new int[]{rr, rc, br, bc, 0});
visited[rr][rc][br][bc] = true;
while (!q.isEmpty()) {
int[] cur = q.poll();
int r1 = cur[0], c1 = cur[1], r2 = cur[2], c2 = cur[3], depth = cur[4];
if (depth >= 10) return -1;
for (int d = 0; d < 4; d++) {
int[] red = moveBead(r1, c1, dx[d], dy[d]);
int[] blue = moveBead(r2, c2, dx[d], dy[d]);
if (map[blue[0]][blue[1]] == 'O') continue;
if (map[red[0]][red[1]] == 'O') return depth + 1;
// 두 구슬이 겹치면 더 멀리 움직인 쪽을 한 칸 뒤로
if (red[0] == blue[0] && red[1] == blue[1]) {
if (red[2] > blue[2]) {
red[0] -= dx[d];
red[1] -= dy[d];
} else {
blue[0] -= dx[d];
blue[1] -= dy[d];
}
}
if (!visited[red[0]][red[1]][blue[0]][blue[1]]) {
visited[red[0]][red[1]][blue[0]][blue[1]] = true;
q.offer(new int[]{red[0], red[1], blue[0], blue[1], depth + 1});
}
}
}
return -1;
}
// [0]: row, [1]: col, [2]: 이동거리
static int[] moveBead(int r, int c, int dr, int dc) {
int moveCount = 0;
while (true) {
if (map[r + dr][c + dc] == '#' || map[r][c] == 'O') break;
r += dr;
c += dc;
moveCount++;
if (map[r][c] == 'O') break;
}
return new int[]{r, c, moveCount};
}
}
코드 길이를 250줄에서 95줄까지 줄였다...
