Algorithm
Java - [BOJ]13459 - 구슬 탈출 + 13460 구슬 탈출2 통합
PlatinumeOlive
2024. 8. 1. 09:37
출처
https://www.acmicpc.net/problem/13459
구슬 탈출 문제
가장 바깥 행과 열이 모두 막혀있고, 밖으로 나갈 수 있는 구멍이 하나 뚫린 상자를 이리저리 기울여서 그 안에 있는 빨간공을 구멍을 통해 꺼낼 수 있는지 판별하는 문제이다. 단, 파란공은 어떠한 경우에도 빠지게 되면 실패로 간주한다.
먼저, 문제의 조건을 추려보면 아래와 같다
- #으로 된 것은 벽 또는 장애물이며, 이 곳으로 공은 갈 수 없다.
- R로 표시된 빨간 공과 B로 표시된 파란공은 각 한칸을 차지하고 있다고 가정한다. 이때 빨간공과 파란공은 같은 위치에 있을 수 없다.
- 빨간공과 파란공은 보드를 기울였을때 동시에 움직인다.
- 빨간 구슬은 10회 이하로만 움직여야 한다.
- 이 문제에서 기울인다 함은, 공이 기울인 방향으로 장애물이나 벽에 부딪혀서 멈추었을 때 까지 공이 굴러감을 의미한다. 중간에 기울임을 멈추어 부딪히지도 않았는데 중간지점에 멈추게 할 수 없다는 걸 전제로 풀어야 한다.
- 기울이는 방향은 왼쪽, 오른쪽, 위, 아래 네가지 이다.
- 빨간공이 먼저 빠지고, 그 뒤에 파란공이 빠지게 되더라도 실패로 간주한다.
이제 이 조건들을 생각하면서 문제를 해결해보겠다.
풀이
우선 이 문제는 BFS를 활용한 시뮬레이션 문제이다. 우리는 map에 대한 정보를 제공 받았고, 보드를 여러 방향으로 기울이며 bfs를 통해 문제에서 원하는 결과를 만들어 내도록 하면된다. (실제로 시뮬레이션을 돌려본다는 느낌)
먼저, 주어진 문자열을 char[][] 배열로 변환하여 인덱스로 편하게 접근할 수 있도록 하였다. 벽을 나타내는 #은 그대로 배열에 넣었고, 나머지는 모두 '.'으로 넣었다. 이때. 최초 빨간공과 파란공, 구멍의 위치는 미리 저장해두도록 하였다.
Node red = null;
Node blue = null;
end = null;
for(int i = 0; i < N; i++) {
String tmp = br.readLine();
for(int j = 0; j < M; j++) {
maps[i][j] = tmp.charAt(j);
if (tmp.charAt(j) != '#') maps[i][j] = '.';
if (tmp.charAt(j) == 'R') red = new Node(i, j, 1);
if (tmp.charAt(j) == 'B') blue = new Node(i, j, 1);
if (tmp.charAt(j) == 'O') end = new Node(i, j, 0);
}
}
이 문제는 어쨋든 최소한의 횟수로 목적지에 도달해야한다는 조건도 포함되어있기 때문에, bfs로 탐색을 진행하려고 한다. 이때 visited배열이 필요한데, 빨간공과 파란공의 visited를 각각 관리하는것이 아닌 한번에 관리해주어야 한다.
이게 무슨 말이냐면, 빨간공과 파란공은 개별적으로 다른 보드에 움직이는 것이 아니고 각각 따로따로 움직이는것이 아니기 때문에, 빨간공과 파란공 두 위치에 대해 visited, 즉 (빨간공 + 파란공)이 있는 위치에 대해 이 상황이 나온적이 있는지 확인해주어야 한다는 뜻이다.
이 visited는 HashSet이나 다른 방법들로 관리해줄 수도 있지만 가장 간단하게 visited[redX][redY][blueX][blueY] 4중 배열을 통해 한번에 visited를 관리해주도록 하겠다.
이제 bfs를 활용하여 시뮬레이션을 돌리고, bfs를 활용하여 기울였을때 공이 움직이는 위치를 계산하면 된다.
public static int bfs(Node r, Node b) {
Deque<Node[]> q = new ArrayDeque<>();
q.addFirst(new Node[]{r, b});
visited[r.x][r.y][b.x][b.y] = true;
while (!q.isEmpty()) {
Node[] now = q.pollLast();
Node red = now[0];
Node blue = now[1];
if (red.depth > 10) {
return 0;
}
if (red.x == end.x && red.y == end.y) {
return 1;
}
for (int i = 0; i < 4; i++) {
Node newRed = new Node(red.x, red.y, red.depth+1);
Node newBlue = new Node(blue.x, blue.y, blue.depth+1);
if (move(dx[i], dy[i], newRed, newBlue)) {
if(isEnd(newRed.x, newRed.y)) return 1;
if(!visited[newRed.x][newRed.y][newBlue.x][newBlue.y]) {
visited[newRed.x][newRed.y][newBlue.x][newBlue.y] = true;
q.addFirst(new Node[]{newRed, newBlue});
}
}
}
}
return 0;
}
static class Node {
int x;
int y;
int depth;
public Node(int x, int y, int depth) {
this.x = x;
this.y = y;
this.depth = depth;
}
}
위 함수는 시뮬레이션을 돌리는 bfs 함수이다.Node[] 배열을 만들어 red,blue를 동시에 큐에 넣었고 각 Node의 Depth를 추가하여 각각 몇번 움직였는지 관리할 수 있도록 하였다.
10회를 초과하여 움직였거나, 구멍 위치에 Red가 도달하였으면 0을 리턴하도록 하였고, 각 탐색에 대해 for문으로 각각 네방향으로 기울여본다. 이때 move()함수를 통해 움직일 수 있다면 move함수에 true를 리턴하도록 하여 큐에 move함수를 통해 움직인 위치를 넣어, 다음 탐색을 진행하도록 구성하였다.
아래는 move()함수이다.
public static boolean move(int directionX, int directionY, Node red, Node blue) {
boolean firstRed = false;
if (directionX == 0 && directionY == 1 && red.y > blue.y) firstRed = true;
if (directionX == 1 && directionY == 0 && red.x > blue.x) firstRed = true;
if (directionX == 0 && directionY == -1 && red.y < blue.y) firstRed = true;
if (directionX == -1 && directionY == 0 && red.x < blue.x) firstRed = true;
while (true) {
int rnx = red.x + directionX;
int rny = red.y + directionY;
if (isPossible(rnx, rny)) {
red.x = rnx;
red.y = rny;
if (isEnd(rnx, rny)) break;
} else {
break;
}
}
while (true) {
int bnx = blue.x + directionX;
int bny = blue.y + directionY;
if (isPossible(bnx, bny)) {
blue.x = bnx;
blue.y = bny;
if (isEnd(bnx, bny)) break;
} else {
break;
}
}
if (isEnd(blue.x, blue.y)) return false;
if (red.x == blue.x && red.y == blue.y) {
if (firstRed) {
blue.x -= directionX;
blue.y -= directionY;
} else {
red.x -= directionX;
red.y -= directionY;
}
}
return true;
}
기울인 방향에 따라서 빨간 구슬과 파란 구슬 중 먼저 움직이는 구슬을 찾아 놓고, 빨간구슬과 파란구슬이 더이상 움직이지 않을 때까지 움직인다.
끝까지 구슬을 움직이다 보면 빨간구슬과 파란구슬이 겹쳐있는 경우가 발생할 수 있다. 두 구슬은 같은 위치에 있을 수 없기 때문에, 이경우에는 아까 구한 정보를 이용하여 나중에 움직인 구슬을 뒤로 한칸 보내었다.
모든 경우를 해당 방법으로 움직여준 후 파란 구슬이 아닌, 빨간 구슬만 구멍으로 들어가는 경우가 존재하는지 확인해 주었다.
13460 구슬 탈출 2
구슬 탈출 2 문제는 구슬 탈출 문제와 조건과 문제가 모두 동일하지만, 단순히 된다 아니다를 판단하는 것이 아닌, 빨간 구슬이 나왔을때 몇 회 움직여서 나오는지를 구하는 문제이다.
필자의 풀이는 Node의 Depth를 이용하여 몇회 움직였는지에 대한 정보를 저장해놓도록 하였다. 따라서 구슬 탈출2 문제에서는 빨간 구슬이 구멍으로 나갈 수 있을 경우 저장해두었던 depth를 리턴해주도록만 바꾼다면, 바로 해결할 수 있다.
구슬 탈출 전체 코드
import java.io.*;
import java.util.*;
public class Main {
static char[][] maps;
static int N, M;
static boolean[][][][] visited;
static int[] dx = {0, 1, 0, -1};
static int[] dy = {1, 0, -1, 0};
static Node end;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
maps = new char[N][M];
visited = new boolean[N][M][N][M];
Node red = null;
Node blue = null;
end = null;
for(int i = 0; i < N; i++) {
String tmp = br.readLine();
for(int j = 0; j < M; j++) {
maps[i][j] = tmp.charAt(j);
if (tmp.charAt(j) != '#') maps[i][j] = '.';
if (tmp.charAt(j) == 'R') red = new Node(i, j, 1);
if (tmp.charAt(j) == 'B') blue = new Node(i, j, 1);
if (tmp.charAt(j) == 'O') end = new Node(i, j, 0);
}
}
bw.write(bfs(red, blue) + "\n");
br.close();
bw.flush();
bw.close();
}
public static int bfs(Node r, Node b) {
Deque<Node[]> q = new ArrayDeque<>();
q.addFirst(new Node[]{r, b});
visited[r.x][r.y][b.x][b.y] = true;
while (!q.isEmpty()) {
Node[] now = q.pollLast();
Node red = now[0];
Node blue = now[1];
if (red.depth > 10) {
return -1;
}
if (red.x == end.x && red.y == end.y) {
return red.depth;
}
for (int i = 0; i < 4; i++) {
Node newRed = new Node(red.x, red.y, red.depth+1);
Node newBlue = new Node(blue.x, blue.y, blue.depth+1);
if (move(dx[i], dy[i], newRed, newBlue)) {
if(isEnd(newRed.x, newRed.y)) return red.depth;
if(!visited[newRed.x][newRed.y][newBlue.x][newBlue.y]) {
visited[newRed.x][newRed.y][newBlue.x][newBlue.y] = true;
q.addFirst(new Node[]{newRed, newBlue});
}
}
}
}
return -1;
}
public static boolean move(int directionX, int directionY, Node red, Node blue) {
boolean firstRed = false;
if (directionX == 0 && directionY == 1 && red.y > blue.y) firstRed = true;
if (directionX == 1 && directionY == 0 && red.x > blue.x) firstRed = true;
if (directionX == 0 && directionY == -1 && red.y < blue.y) firstRed = true;
if (directionX == -1 && directionY == 0 && red.x < blue.x) firstRed = true;
while (true) {
int rnx = red.x + directionX;
int rny = red.y + directionY;
if (isPossible(rnx, rny)) {
red.x = rnx;
red.y = rny;
if (isEnd(rnx, rny)) break;
} else {
break;
}
}
while (true) {
int bnx = blue.x + directionX;
int bny = blue.y + directionY;
if (isPossible(bnx, bny)) {
blue.x = bnx;
blue.y = bny;
if (isEnd(bnx, bny)) break;
} else {
break;
}
}
if (isEnd(blue.x, blue.y)) return false;
if (red.x == blue.x && red.y == blue.y) {
if (firstRed) {
blue.x -= directionX;
blue.y -= directionY;
} else {
red.x -= directionX;
red.y -= directionY;
}
}
return true;
}
public static boolean isPossible(int x, int y) {
return maps[x][y] == '.';
}
public static boolean isEnd(int x, int y) {
return (end.x == x && end.y == y);
}
static class Node {
int x;
int y;
int depth;
public Node(int x, int y, int depth) {
this.x = x;
this.y = y;
this.depth = depth;
}
}
}
구슬 탈출 2 전체 코드
import java.io.*;
import java.util.*;
public class Main {
static char[][] maps;
static int N, M;
static boolean[][][][] visited;
static int[] dx = {0, 1, 0, -1};
static int[] dy = {1, 0, -1, 0};
static Node end;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
maps = new char[N][M];
visited = new boolean[N][M][N][M];
Node red = null;
Node blue = null;
end = null;
for(int i = 0; i < N; i++) {
String tmp = br.readLine();
for(int j = 0; j < M; j++) {
maps[i][j] = tmp.charAt(j);
if (tmp.charAt(j) != '#') maps[i][j] = '.';
if (tmp.charAt(j) == 'R') red = new Node(i, j, 1);
if (tmp.charAt(j) == 'B') blue = new Node(i, j, 1);
if (tmp.charAt(j) == 'O') end = new Node(i, j, 0);
}
}
bw.write(bfs(red, blue) + "\n");
br.close();
bw.flush();
bw.close();
}
public static int bfs(Node r, Node b) {
Deque<Node[]> q = new ArrayDeque<>();
q.addFirst(new Node[]{r, b});
visited[r.x][r.y][b.x][b.y] = true;
while (!q.isEmpty()) {
Node[] now = q.pollLast();
Node red = now[0];
Node blue = now[1];
if (red.depth > 10) {
return -1;
}
if (red.x == end.x && red.y == end.y) {
return red.depth;
}
for (int i = 0; i < 4; i++) {
Node newRed = new Node(red.x, red.y, red.depth+1);
Node newBlue = new Node(blue.x, blue.y, blue.depth+1);
if (move(dx[i], dy[i], newRed, newBlue)) {
if(isEnd(newRed.x, newRed.y)) return red.depth;
if(!visited[newRed.x][newRed.y][newBlue.x][newBlue.y]) {
visited[newRed.x][newRed.y][newBlue.x][newBlue.y] = true;
q.addFirst(new Node[]{newRed, newBlue});
}
}
}
}
return -1;
}
public static boolean move(int directionX, int directionY, Node red, Node blue) {
boolean firstRed = false;
if (directionX == 0 && directionY == 1 && red.y > blue.y) firstRed = true;
if (directionX == 1 && directionY == 0 && red.x > blue.x) firstRed = true;
if (directionX == 0 && directionY == -1 && red.y < blue.y) firstRed = true;
if (directionX == -1 && directionY == 0 && red.x < blue.x) firstRed = true;
while (true) {
int rnx = red.x + directionX;
int rny = red.y + directionY;
if (isPossible(rnx, rny)) {
red.x = rnx;
red.y = rny;
if (isEnd(rnx, rny)) break;
} else {
break;
}
}
while (true) {
int bnx = blue.x + directionX;
int bny = blue.y + directionY;
if (isPossible(bnx, bny)) {
blue.x = bnx;
blue.y = bny;
if (isEnd(bnx, bny)) break;
} else {
break;
}
}
if (isEnd(blue.x, blue.y)) return false;
if (red.x == blue.x && red.y == blue.y) {
if (firstRed) {
blue.x -= directionX;
blue.y -= directionY;
} else {
red.x -= directionX;
red.y -= directionY;
}
}
return true;
}
public static boolean isPossible(int x, int y) {
return maps[x][y] == '.';
}
public static boolean isEnd(int x, int y) {
return (end.x == x && end.y == y);
}
static class Node {
int x;
int y;
int depth;
public Node(int x, int y, int depth) {
this.x = x;
this.y = y;
this.depth = depth;
}
}
}