https://www.acmicpc.net/problem/13460
보드판 : 세로 크기 = N, 가로 크기 = M
게임의 목표 = 빨간 구슬을 구멍을 통해서 빼내는 것. 이때 파란 구슬이 구멍에 들어가면 안 된다.
구슬 이동 방법 = 보드판을 왼쪽, 오른쪽, 위쪽, 아래쪽으로 기울이기의 4가지 방법
→ 기울이면 빨간 구슬 뿐만 아니라 파란 구슬도 이동한다.
한 번 기울이면 구슬이 더 이상 이동하지 못할 때까지 이동한다. = 도중에 멈추기 불가능
최소 몇 번 만에 빨간 구슬을 구멍을 통해 빼낼 수 있을까?
즉 목표는 빨간 구슬을 최단 거리로 구멍(목적지)까지 이동시키는 것이다. 단, 이때 파란 구슬이 구멍에 들어가면 안 된다.
우선은 RED, BLUE, GOAL의 초기 위치를 파악해 두자.
어떻게 구슬을 이동시키는 것인가. 구슬 이동은 판을 기울이는 것으로 이동한다. 결국 해당 방향으로 더 이상 이동하지 못할 때까지 이동하는 것이다.
그런데 구슬이 두 종류가 존재한다. 또한 두 구슬이 동시에 이동한다.
두 구슬이 동일한 위치로 가는 것이 아니면 각각 움직이면 되니까 문제는 없다.
그런데 한 위치를 목표로 이동하게 되면 문제가 된다.
우선 해당 위치로 먼저 도착하는 구슬을 정해야 한다. 그리고 그 이후에 도착하는 구슬을 왔던 방향의 반대로 1개만큼 이동시키면 될 것 같다.
이동하면서 과정에 구멍이 있는지 파악을 해야 한다. 이동하는 과정에 구멍에 빠지는 경우에도 탈출한 것이다.
빨간 구슬이 구멍에 빠졌다고 해결이 된 것이 아니다. 파란 구슬이 뒤이어 빠지게 되면 해당 경로는 불가능한 경로가 된다.
백트랙킹이 필요하다.
dfs를 통해 이동 방향을 변경해 가며 탐색해 나간다. 그 과정에서 파란 구슬이 구멍에 빠지면 해당 경로는 불가능한 경로가 되기 때문에 백트랙킹을 한다.
특정 방향 이동 방법에 대해 생각해 보자. 해당 뱡향을 d라고 하겠다.
두 구슬의 현재 위치를 알아야 한다.
이동 후 두 구슬의 위치가 동일하다면 늦게 도착하는 구슬은 위치 보정을 해준다.
그 이외의 경우에는 그냥 구슬을 목표점까지 이동시키면 된다.
여기서 목표점이란 ‘#’ 즉 벽을 만날 때까지이다.
각각 이동하면서 매 위치마다 구멍이 존재하는지 확인해야 한다.
위의 두 특수 경우에는 구멍이 존재한다면 무조건 해당 경로는 불가능한 경로이다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Test {
static FastReader scan = new FastReader();
static int N,M;
static char[][] board;
static int[] initialRed = new int[2];
static int[] initialBlue = new int[2];
static boolean redGoal = false;
static boolean blueGoal = false;
static int minPath = Integer.MAX_VALUE;
static int[][] DIRECTION = {{-1, 0}, {0, -1}, {0, 1}, {1, 0}}; //상좌우하
static void input() {
N = scan.nextInt();
M = scan.nextInt();
board = new char[N][M];
for (int i = 0; i < N; i++) {
board[i] = scan.nextLine().toCharArray();
}
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
if (board[i][j] == 'R') {
initialRed = new int[]{i, j};
} else if (board[i][j] == 'B') {
initialBlue = new int[]{i, j};
}
}
}
}
static void dfs(int depth, int redR, int redC, int blueR,int blueC) {
if (blueGoal) return; // blue가 골에 도달하면 안된다.
if (redGoal && !blueGoal) {
minPath = Math.min(minPath, depth);
return;
}
for (int d = 0; d < 4; d++) {
if (depth < 10) {
int[][] newPosition = move(d, redR, redC, blueR, blueC);
dfs(depth + 1, newPosition[0][0], newPosition[0][1], newPosition[1][0], newPosition[1][1]);
redGoal = false;
blueGoal = false;
}
}
}
static int[][] move(int d, int redR, int redC, int blueR, int blueC) {
int[] redPosition = new int[2];
int[] bluePosition = new int[2];
int redDistance = 0;
int blueDistance = 0;
int newRedR = redR;
int newRedC = redC;
while (isValidPosition(newRedR, newRedC) && board[newRedR][newRedC] != '#') {
newRedR += DIRECTION[d][0];
newRedC += DIRECTION[d][1];
redDistance++;
if (board[newRedR][newRedC] == 'O') {
redGoal = true;
break;
} else if (board[newRedR][newRedC] == '#') {
newRedR += DIRECTION[3-d][0];
newRedC += DIRECTION[3-d][1];
redDistance--;
break;
}
}
int newBlueR = blueR;
int newBlueC = blueC;
while (isValidPosition(newBlueR, newBlueC) && board[newBlueR][newBlueC] != '#') {
newBlueR += DIRECTION[d][0];
newBlueC += DIRECTION[d][1];
blueDistance++;
if (board[newBlueR][newBlueC] == 'O') {
blueGoal = true;
break;
} else if (board[newBlueR][newBlueC] == '#') {
newBlueR += DIRECTION[3-d][0];
newBlueC += DIRECTION[3-d][1];
blueDistance--;
break;
}
}
if (newRedR == newBlueR && newRedC == newBlueC) {
if (redDistance < blueDistance) {
newBlueR += DIRECTION[3-d][0];
newBlueC += DIRECTION[3-d][1];
} else {
newRedR += DIRECTION[3-d][0];
newRedC += DIRECTION[3-d][1];
}
}
// 이동 끝
redPosition[0] = newRedR;
redPosition[1] = newRedC;
bluePosition[0] = newBlueR;
bluePosition[1] = newBlueC;
return new int[][]{redPosition, bluePosition};
}
static boolean isValidPosition(int r, int c) {
return r >= 0 && r < N && c >= 0 && c < M;
}
public static void main(String[] args) {
input();
dfs(0, initialRed[0], initialRed[1], initialBlue[0], initialBlue[1]);
int answer = -1;
if (minPath != Integer.MAX_VALUE) {
answer = minPath;
}
System.out.println(answer);
}
static class FastReader {
BufferedReader br;
StringTokenizer st;
public FastReader() {
br = new BufferedReader(new InputStreamReader(System.in));
}
String next() {
while (st == null || !st.hasMoreElements()) {
try {
st = new StringTokenizer(br.readLine());
} catch (IOException e) {
e.printStackTrace();
}
}
return st.nextToken();
}
String nextLine() {
String str = "";
try {
str = br.readLine();
} catch (IOException e) {
e.printStackTrace();
}
return str;
}
int nextInt() {
return Integer.parseInt(next());
}
}
}
중복된 부분이 좀 있어 메서드 분리등의 리팩토링이 필요하지만 정답은 맞게 처리됐다.
하지만 지금 방문처리를 하지 않고 있기 때문에 중복된 방향으로 가지 않아도 되는데 같은 방향을 계속 시도하고 있다. 이런 부분을 해결하기 위해서는 방문처리를 하는 별도의 배열이 필요할 것이다.
또한 최소 이동 횟수를 찾는 문제이다. DFS보다는 BFS가 더 어울린다.
BFS로 풀어봄과 동시에 시뮬레이션 문제이니 객체지향적인 관점을 좀 도입해 보자.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Objects;
import java.util.Queue;
import java.util.Set;
import java.util.StringTokenizer;
public class Test {
static FastReader scan = new FastReader();
static int N, M;
static char[][] board;
// 위치를 관리할 클래스
static class Point {
private final int row;
private final int col;
Point(int row, int col) {
this.row = row;
this.col = col;
}
int getRow() {
return this.row;
}
int getCol() {
return this.col;
}
// 같은 지점인지 판단하기 위한 간단한 equals
@Override
public boolean equals(Object obj) {
if (this == obj) return true;
if (!(obj instanceof Point)) return false;
Point point = (Point) obj;
return this.row == point.getRow() && this.col == point.getCol();
}
@Override
public int hashCode() {
return Objects.hash(row, col);
}
}
// 방향을 관리하는 enum
enum Direction {
UP(-1, 0),
DOWN(1, 0),
LEFT(0, -1),
RIGHT(0, 1);
private final int deltaRow;
private final int deltaCol;
Direction(int deltaRow, int deltaCol) {
this.deltaRow = deltaRow;
this.deltaCol = deltaCol;
}
public int getDeltaRow() {
return deltaRow;
}
public int getDeltaCol() {
return deltaCol;
}
}
// 보드판 상태
static class Board {
private final char[][] board;
private Point red;
private Point blue;
private final int moveCount;
Board(char[][] board, Point red, Point blue, int moveCount) {
this.board = board;
this.red = red;
this.blue = blue;
this.moveCount = moveCount;
}
// 이동 후 보드판의 상태를 반환하는 메서드
Board move(Direction dir) {
char[][] newBoard = deepCopy(board);
Point newRed = movePoint(newBoard, red, dir);
Point newBlue = movePoint(newBoard, blue, dir);
if (newRed.equals(newBlue) && newBoard[newRed.getRow()][newRed.getCol()] != 'O') {
// 레드랑 블루랑 같은 위치인데 골이 아닌경우 -> 위치 조정 필요
if (getDistance(red, newRed) < getDistance(blue, newBlue)) {
// 레드가 더 가까웠는 경우
newBlue = moveBack(newBlue, dir);
} else {
newRed = moveBack(newRed, dir);
}
}
// 보드판 내용 수정
if (!red.equals(newRed)) {
changeBoard(newBoard, red, newRed, 'R');
}
if (!blue.equals(newBlue)) {
changeBoard(newBoard, blue, newBlue, 'B');
}
// 1회 이동이 끝난 뒤 새로운 보드판 상황 반환
return new Board(newBoard, newRed, newBlue, moveCount + 1);
}
private void changeBoard(char[][] board, Point p1, Point p2, char type) {
board[p1.getRow()][p1.getCol()] = '.';
if (board[p2.getRow()][p2.getCol()] != 'O') {
board[p2.getRow()][p2.getCol()] = type;
}
}
private int getDistance(Point p1, Point p2) {
return Math.abs(p1.getRow() - p2.getRow()) + Math.abs(p1.getCol() - p2.getCol());
}
private Point moveBack(Point point, Direction dir) {
return new Point(point.getRow() - dir.getDeltaRow(), point.getCol() - dir.getDeltaCol());
}
private Point movePoint(char[][] board, Point start, Direction dir) {
int row = start.getRow();
int col = start.getCol();
while (board[row + dir.getDeltaRow()][col + dir.getDeltaCol()] != '#' && board[row][col] != 'O') {
// 다음위치가 # 이면 이동하면 안됨.
row += dir.getDeltaRow();
col += dir.getDeltaCol();
}
return new Point(row, col);
}
private char[][] deepCopy(char[][] board) {
return Arrays.stream(board)
.map(char[]::clone)
.toArray(char[][]::new);
}
public Point getRed() {
return red;
}
public Point getBlue() {
return blue;
}
public int getMoveCount() {
return moveCount;
}
public char[][] getBoard() {
return board;
}
}
static int bfs() {
Point red = null;
Point blue = null;
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
if (board[i][j] == 'R') {
red = new Point(i, j);
} else if (board[i][j] == 'B') {
blue = new Point(i, j);
}
}
}
Queue<Board> q = new LinkedList<>(); // 보드판 상태를 가지는 큐
Set<String> visited = new HashSet<>();
Board initialState = new Board(board, red, blue, 0);
q.offer(initialState);
visited.add(stateToString(initialState));
while (!q.isEmpty()) {
Board currentState = q.poll();
if (currentState.moveCount > 10) break; // 10회 이상 이동한 상태
if (currentState.getBoard()[currentState.getBlue().getRow()][currentState.getBlue().getCol()] == 'O') continue; // 블루가 목적지에 도달한 경우
if (currentState.getBoard()[currentState.getRed().getRow()][currentState.getRed().getCol()] == 'O') {
return currentState.getMoveCount();
}
for (Direction dir : Direction.values()) {
Board nextState = currentState.move(dir);
String stateKey = stateToString(nextState);
if (!visited.contains(stateKey)) {
// 처음 방문하는 상태의 경우
visited.add(stateKey);
q.offer(nextState);
}
}
}
return -1; // 모든 탐색이 끝났는데 답을 못찾았다.
}
static String stateToString(Board board) {
return board.getRed().getRow() + "," + board.getRed().getCol() + "," + board.getBlue().getRow() + "," +board.getBlue().getCol();
}
static void input() {
N = scan.nextInt();
M = scan.nextInt();
board = new char[N][M];
for (int i = 0; i < N; i++) {
board[i] = scan.nextLine().toCharArray();
}
}
public static void main(String[] args) {
input();
int answer = bfs();
System.out.println(answer);
}
static class FastReader {
BufferedReader br;
StringTokenizer st;
public FastReader() {
br = new BufferedReader(new InputStreamReader(System.in));
}
String next() {
while (st == null || !st.hasMoreElements()) {
try {
st = new StringTokenizer(br.readLine());
} catch (IOException e) {
e.printStackTrace();
}
}
return st.nextToken();
}
String nextLine() {
String str = "";
try {
str = br.readLine();
} catch (IOException e) {
e.printStackTrace();
}
return str;
}
int nextInt() {
return Integer.parseInt(next());
}
}
}
하고 나서 보니까 Direction의 Enum 도입은 오히려 복잡성만 증가시켰다는 생각이 든다. 그냥 배열로 관리하는 게 더 직관적이었을 것 같다. 또한 getter의 경우에도 알고리즘 문제에서는 쓸데없는 코드의 길이만 늘린다.
