문제 정보
https://www.acmicpc.net/problem/13460
문제 파악
문제 조건
3 <= N, M <= 10
문제 내용
보드에는 '.'(빈칸), '#'(벽), 'O'(구멍), 'B'(파란 구슬), 'R'(빨간 구슬) 총 5가지 요소가 존재한다
각 구슬들은 빈칸을 통해 이동할 수 있으며, 벽으로는 이동할 수 없다
주어진 보드를 기울여서(왼쪽, 오른쪽, 위, 아래) 구슬을 구멍으로 통과시키되, 빨간 구슬만 통과시켜야 한다
위에 첨부된 사진을 생각하면 이해가 될 듯 하다.
위 보드의 초기 상태가 하늘을 향하고 있다고 가정하고, 위 사진처럼 아래로 기울인다면 사진의 공이 아래로 쭉 내려와서 오른쪽 아래 모서리에 위치하게 될 것이다.
그리고 다시 하늘을 보게 놔두면, 총 한번 기울인 것이 되는 것이다.
하지만, 문제에서는 공이 2개이다. 아래 예제를 보자.
(왼쪽으로 기울인다면)
####### #######
#...RB# #RB...#
#.##### #.#####
#.....# #.....#
#####.# #####.#
#O....# #O....#
####### #######
1 21번째 상태에서 공 두개가 나란히 위치해 있다.
이 판을 왼쪽으로 기울인다면, 두 공이 겹치는 것이 아닌 나란히 이동하여 왼쪽으로 갈 수 있는 최대의 위치에서 멈추게 된다. (2번의 상태)
2번의 상태에서 아래로 기울인다면,
(아래로 기울인다면)
####### #######
#RB...# #.B...#
#.##### #.#####
#.....# #R....#
#####.# #####.#
#O....# #O....#
####### #######
2 33번처럼 빨간 공만 아래로 내려오게 될 것이다.
코드에서 위와 같이 1->2번으로 넘어가는 상태를 구현하는 것이 이 문제의 핵심이 아닐까 생각이 든다.
풀이
풀이한 내용
많은 시행착오가 있었고, 결국 문제를 풀었지만 visited(방문 처리)를 하는 부분에 있어서는 다른 블로그의 도움을 받을 수밖에 없었다
과정을 천천히 설명해 보도록 하겠다
visited = new boolean[N][M][N][M];
이는 visited[ry][rx][by][bx] 는 (ry, rx), (by, bx) 위치에서 기울인 적이 있는지를 저장하는 4차원 배열이다.
일반적인 그래프 탐색 풀이였다면, 따로 방문했는지를 판단했을 테지만 그럴 수 없는 이유는
7 7
#######
#..R#B#
#.#####
#.....#
#####.#
#O....#
#######위와 같이 파란 공은 움직일 수 없는데, 그렇게 되면 해당 위치는 계속 방문되었음을 나타낼 것이고 문제를 정상적으로 풀이할 수 없는 상황이 나타날 것이다.
따라서 두 공의 좌표를 기준으로 방문했음을 나타낸다면, 위 경우에서 B의 좌표는 변하지 않지만 R의 좌표는 계속 변하기 때문에 계속해서 탐색해 나아갈 수 있음을 의미한다
class Ball {
int Ry;
int Rx;
int By;
int Bx;
int count;
public Ball(int ry, int rx, int by, int bx, int count) {
Ry = ry;
Rx = rx;
By = by;
Bx = bx;
this.count = count;
}
}너비 우선 탐색을 진행할 때, 큐에 넣을 클래스를 따로 선언해 주었다.
기울인 횟수는 어느 공 하나에 연관되는 것이 아니라, 두 공의 위치에 연관되어 있기 때문에 현재 문제의 답인 기울인 횟수를 저장하기 위하여 각 공의 좌표와 count(기울인 횟수)를 함께 클래스로 저장했다
static int[][] around = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
private static int solve(Ball pos) {
Queue<Ball> queue = new LinkedList<>();
queue.add(pos);
while (!queue.isEmpty()) {
Ball current = queue.poll();
int Ry = current.Ry;
int Rx = current.Rx;
int By = current.By;
int Bx = current.Bx;
int count = current.count;
for (int[] a : around) {
int[] moveR = move(Ry, Rx, a[0], a[1]);
int[] moveB = move(By, Bx, a[0], a[1]);BFS를 수행하는 solve 메서드의 일부이다.
큐에서 위치를 뽑고 current 라고 지칭한다. 각 좌표를 변수에 담아놓고 탐색을 준비한다.
for loop의 대상인 around 는 2차원 배열이다(상하좌우가 저장되어 있다)
여기서 move() 메서드를 통하여 기울였을 때의 공의 위치를 계산하는데, 위에서 언급했듯 공은 한칸씩 움직이는 것이 아닌 갈 수 있는 최대로 움직이기 때문에
private static int[] move(int y, int x, int moveY, int moveX) {
while (board[y + moveY][x + moveX] != '#') {
y += moveY;
x += moveX;
if (board[y][x] == 'O') {
break;
}
}
return new int[] {y, x};
}벽에 닿기 전까지 해당 공을 움직이면서, 결과적으로 멈춘 위치를 리턴하게 된다
다만, 이동하다가 구멍이 존재한다면 벽의 여부와는 상관 없이 구멍에 공이 빠지게 되므로
이에 유의해서 구멍에 닿았을 때에는 반복을 종료하고 해당 위치를 리턴한다
if (board[moveB[0]][moveB[1]] == 'O') {
continue;
}
if (board[moveR[0]][moveR[1]] == 'O') {
return nextCount;
}문제의 조건 중 하나로, 빨간 공만 구멍으로 빠져나와야 하고 파란 공은 빠져 나오면 안되므로
파란 공의 위치가 구멍인지를 먼저 판별한다.
빨간 공과 파란 공이 동시에 빠져도 문제지만, 파란 공만 빠져도 문제가 되므로 파란 공이 빠지면 일단 더이상 진행할 수 없는 케이스가 된다
추가로 빨간 공이 구멍에 닿게 되면, BFS의 특징에 따라 최소 경우이므로 이를 리턴하게 된다
// 기존 위치를 비교한다. 기존 위치가 R B 순으로 있었는데, 오른쪽으로 이동 중 겹쳤다면 R을 하나 빼주어야(서쪽) 함
// 1 4 -> 4 4 -> 3 4 (0, 1) 기존에 더 작았던 거에서 빼줌
// 1 4 -> 1 1 -> 1 2 (0, -1) 기존에 더 컷던 거에서 빼줌
// 1 4 -> 4 4 -> 3 4 (1, 0) 기존에 더 작았던 거에서 빼줌
// 이동 방향이 양수인 경우와 음수인 경우로 나눔
if (moveR[0] == moveB[0] && moveR[1] == moveB[1]) {
if (a[0] > 0) {
if (Ry > By) {
moveB[0] -= a[0];
} else {
moveR[0] -= a[0];
}
}
if (a[0] < 0) {
if (Ry > By) {
moveR[0] -= a[0];
} else {
moveB[0] -= a[0];
}
}
if (a[1] > 0) {
if (Rx > Bx) {
moveB[1] -= a[1];
} else {
moveR[1] -= a[1];
}
}
if (a[1] < 0) {
if (Rx > Bx) {
moveR[1] -= a[1];
} else {
moveB[1] -= a[1];
}
}앞서 주의해야 할 점으로 언급했던 공이 겹치는 경우이다
위 move() 메서드의 결과로 벽 이전까지 공을 이동시키므로, 두 공의 위치가 겹쳐 있을 수도 있다
만약 두 공이 수직 이동(아래 또는 위) 했다면, 이전 공의 위치의 수직 좌표(y좌표)를 비교해야 하고,
수평 이동(왼쪽 혹은 오른쪽) 했다면, 이전 공의 위치에 수평 좌표(x좌표)를 비교해야 한다.
(왼쪽으로 기울인다면)
####### #######
#...RB# #RB...#
#.##### #.#####
#.....# #.....#
#####.# #####.#
#O....# #O....#
####### #######
1 2앞선 예제인데, 이 경우 1->2를 위해 왼쪽으로 기울이면 코드상에서 R과 B의 위치는 동일한 좌표(1, 1)를 갖게 될 것이다
이 경우 이전 공의 좌표를 비교하면, B는 R의 오른쪽에 위치(x좌표)했었기 때문에 B의 이동 좌표에서 한 칸 오른쪽(-(-1)) 이동 시켜주면 된다.
이는 조금 이해가 필요한 부분이라, 개인적으로 직접 그려보며 이해하는 편이 빠를 것 같다.
어렵지는 않을 것이다.
if (!visited[moveR[0]][moveR[1]][moveB[0]][moveB[1]]) {
visited[moveR[0]][moveR[1]][moveB[0]][moveB[1]] = true;
queue.add(new Ball(moveR[0], moveR[1], moveB[0], moveB[1], nextCount));
}이후 현재 두 공의 좌표를 시작으로 계산한 적이 있는지를 판별한다.
만약 없다면, 계산했음을 표시(true) 하고 큐에 다음 위치를 추가하고, 있다면 추가적인 작업을 하지 않으면 된다.
여기까지 풀었다면 문제를 다 푼 것이다.
코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
private static int N;
private static int M;
private static char[][] board;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
// 보드의 크기, 세로 N, 가로 M
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
int[] red = new int[2];
int[] blue = new int[2];
board = new char[N][M];
visited = new boolean[N][M][N][M];
for (int n = 0; n < N; n++) {
String line = br.readLine();
for (int m = 0; m < M; m++) {
board[n][m] = line.charAt(m);
if (board[n][m] == 'R') {
red[0] = n;
red[1] = m;
} else if (board[n][m] == 'B') {
blue[0] = n;
blue[1] = m;
}
}
}
visited[red[0]][red[1]][blue[0]][blue[1]] = true;
/**
* 빨간 구슬을 구멍을 통해서 빼내는 것이 목표
* 파란 구슬이 구멍에 들어가면 안됨
*/
int result = solve(new Ball(red[0], red[1], blue[0], blue[1], 0));
System.out.println(result <= 10 ? result : -1);
}
static boolean[][][][] visited;
static int[][] around = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
private static int solve(Ball pos) {
Queue<Ball> queue = new LinkedList<>();
queue.add(pos);
while (!queue.isEmpty()) {
Ball current = queue.poll();
int Ry = current.Ry;
int Rx = current.Rx;
int By = current.By;
int Bx = current.Bx;
int count = current.count;
for (int[] a : around) {
int[] moveR = move(Ry, Rx, a[0], a[1]);
int[] moveB = move(By, Bx, a[0], a[1]);
int nextCount = count + 1;
if (board[moveB[0]][moveB[1]] == 'O') {
continue;
}
if (board[moveR[0]][moveR[1]] == 'O') {
return nextCount;
}
// 기존 위치를 비교한다. 기존 위치가 R B 순으로 있었는데, 오른쪽으로 이동 중 겹쳤다면 R을 하나 빼주어야(서쪽) 함
// 1 4 -> 4 4 -> 3 4 (0, 1) 기존에 더 작았던 거에서 빼줌
// 1 4 -> 1 1 -> 1 2 (0, -1) 기존에 더 컷던 거에서 빼줌
// 1 4 -> 4 4 -> 3 4 (1, 0) 기존에 더 작았던 거에서 빼줌
// 이동 방향이 양수인 경우와 음수인 경우로 나눔
if (moveR[0] == moveB[0] && moveR[1] == moveB[1]) {
if (a[0] > 0) {
if (Ry > By) {
moveB[0] -= a[0];
} else {
moveR[0] -= a[0];
}
}
if (a[0] < 0) {
if (Ry > By) {
moveR[0] -= a[0];
} else {
moveB[0] -= a[0];
}
}
if (a[1] > 0) {
if (Rx > Bx) {
moveB[1] -= a[1];
} else {
moveR[1] -= a[1];
}
}
if (a[1] < 0) {
if (Rx > Bx) {
moveR[1] -= a[1];
} else {
moveB[1] -= a[1];
}
}
}
if (!visited[moveR[0]][moveR[1]][moveB[0]][moveB[1]]) {
visited[moveR[0]][moveR[1]][moveB[0]][moveB[1]] = true;
queue.add(new Ball(moveR[0], moveR[1], moveB[0], moveB[1], nextCount));
}
}
}
return -1;
}
private static int[] move(int y, int x, int moveY, int moveX) {
while (board[y + moveY][x + moveX] != '#') {
y += moveY;
x += moveX;
if (board[y][x] == 'O') {
break;
}
}
return new int[] {y, x};
}
}
class Ball {
int Ry;
int Rx;
int By;
int Bx;
int count;
public Ball(int ry, int rx, int by, int bx, int count) {
Ry = ry;
Rx = rx;
By = by;
Bx = bx;
this.count = count;
}
}
Source Code on GitHub
댓글