https://www.acmicpc.net/problem/13460
문제
스타트링크에서 판매하는 어린이용 장난감 중에서 가장 인기가 많은 제품은 구슬 탈출이다. 구슬 탈출은 직사각형 보드에 빨간 구슬과 파란 구슬을 하나씩 넣은 다음, 빨간 구슬을 구멍을 통해 빼내는 게임이다.
보드의 세로 크기는 N, 가로 크기는 M이고, 편의상 1×1크기의 칸으로 나누어져 있다. 가장 바깥 행과 열은 모두 막혀져 있고, 보드에는 구멍이 하나 있다. 빨간 구슬과 파란 구슬의 크기는 보드에서 1×1크기의 칸을 가득 채우는 사이즈이고, 각각 하나씩 들어가 있다. 게임의 목표는 빨간 구슬을 구멍을 통해서 빼내는 것이다. 이때, 파란 구슬이 구멍에 들어가면 안 된다.
이때, 구슬을 손으로 건드릴 수는 없고, 중력을 이용해서 이리 저리 굴려야 한다. 왼쪽으로 기울이기, 오른쪽으로 기울이기, 위쪽으로 기울이기, 아래쪽으로 기울이기와 같은 네 가지 동작이 가능하다.
각각의 동작에서 공은 동시에 움직인다. 빨간 구슬이 구멍에 빠지면 성공이지만, 파란 구슬이 구멍에 빠지면 실패이다. 빨간 구슬과 파란 구슬이 동시에 구멍에 빠져도 실패이다. 빨간 구슬과 파란 구슬은 동시에 같은 칸에 있을 수 없다. 또, 빨간 구슬과 파란 구슬의 크기는 한 칸을 모두 차지한다. 기울이는 동작을 그만하는 것은 더 이상 구슬이 움직이지 않을 때 까지이다.
보드의 상태가 주어졌을 때, 최소 몇 번 만에 빨간 구슬을 구멍을 통해 빼낼 수 있는지 구하는 프로그램을 작성하시오.
입력
첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B' 로 이루어져 있다. '.'은 빈 칸을 의미하고, '#'은 공이 이동할 수 없는 장애물 또는 벽을 의미하며, 'O'는 구멍의 위치를 의미한다. 'R'은 빨간 구슬의 위치, 'B'는 파란 구슬의 위치이다.
입력되는 모든 보드의 가장자리에는 모두 '#'이 있다. 구멍의 개수는 한 개 이며, 빨간 구슬과 파란 구슬은 항상 1개가 주어진다.
출력
최소 몇 번 만에 빨간 구슬을 구멍을 통해 빼낼 수 있는지 출력한다. 만약, 10번 이하로 움직여서 빨간 구슬을 구멍을 통해 빼낼 수 없으면 -1을 출력한다.
[ 문제 파악 ]
길찾기 문제? 바로 전형적인 BackTracking 문제라고 생각한다.
빨간 구슬을 기준으로 갈 수 있는 동서남북의 방향을 기준으로 backTracking을 하면 된다고 생각했다.
그런데 파란 구슬이 문제였다. 만약 파란구슬을 살짝 치워놨을 때, 즉 빨간 구슬을 기준으로 기울이는 것이 아니라 파란 구슬을 기준으로 경로를 (빨간 구슬이 갈 경로에서 치워놓는 목적으로) 결정해야, 더욱 최단 거리가 나타난다면?
그런 경우가 있을 수 있느냐? 를 먼저 생각해봤다.
무조건 빨간 구슬을 기준으로 움직이면 된다고 생각했는데, 파란 구슬의 움직임까지 수동적이 아닌, 능동적인 개체로, 백트래킹이 포함시켜야 하는가?
일단, 상식적인 생각으로는 빨간 구슬이 갈 수 있는 모든 경로만으로 생각하는 게 맞다는 결론이 났다. 그렇지 않으면 너무 복잡해질 문제인 것 같기도 하고, 파란 구슬의 경로는 빨간 구슬의 기준으로만 수동적으로 생각하기로 했다.
빨간 구슬은 왔던 길을 되돌아 갈 수 있는가?
왔던 길을 되돌아가는 경우는 해당 경로에서 가능한 성공의 길이 없을 때 뿐이라고 생각했다. 그렇다면 실패의 경우가 아니고, 새로운 길을 찾는 경우에는 왔던 길을 포함시키면 안된다.
실패 조건에 대해서 생각해보기.
1. 빨간 구슬이 백트래킹을 통해 길을 전부 찾았는데, 결국 찾지 못해서 다시 시작점으로 되돌아온 경우.
2. 성공하지 못했는데, 기울이는 행위를 10번 이상 이미 해버린 경우.
3. 파란 구슬이 구멍에 들어가버린 경우.
4. 빨간 구슬이 더이상 움직일 수 없는 경우. (?) - ex 사방이 막혀있거나..
실패조건 4. 에 대해서 생각해보다가, 만약 이런 상황에서는 어떻게 해야할 지 생각이 들었다.
빨간 공이 사방에 막혀있지만, 한 쪽 방면은 파란 공이 막고 있는 것이다. 그러나 파란 공은 기울였을 때 함께 움직일 가능성이 있다. 그렇다면 빨간 공을 움직일 수 있는 방면을 계산할 때, 파란 공이 있는 곳은 막혀있다고 판단하지 않아도 되는 것일까?
실제로 위와 같은 경우는 UP -> LEFT -> DOWN 으로 이동하면 3번만에 빨간 공만이 구멍에 도달할 수 있다.
지금까지 몇 번 움직였는지는 어떻게 저장할 것인가?
일단은 `재귀 함수를 이용해서 파라미터로 넘기기` 밖에 생각이 나지 않는다...
가장 최솟값은 static int 로 선언해서, 구멍에 도달했을 때 더 작은 이동 횟수가 나온다면 갱신해줄 생각이다.
논리의 큰 흐름을 생각해보자.
1. 빨간 구슬의 현재 위치를 구한다.
2. 빨간 구슬의 현재 위치에서 상하좌우 중 기울여서 움직일 수 있는 곳을 구한다.
3. 기울이면서 지나가는 길목(최종 도달 좌표 포함)에 구멍이 있는가?
4. 구멍이 있다면 성공(파란 구슬도 같이 들어가면 실패), 없다면 새로운 좌표로 이동한다.
구슬이 이동하는 중에 일어날 일들
1. 빨간 구슬과 파란 구슬이 각기 다른 경로에 있을 시에는 빨간 구슬 -> 파란 구슬 순으로 움직이면 된다.
2. 빨간 구슬과 파란 구슬이 같은 경로 라인에 있을 시에는 어떤 구슬을 먼저 움직여야 하는지 순서를 고려해서 움직여야 한다.
3. 움직이는 도중에, 두 구슬 모두 구멍을 만날 수 있다. 혹은 한 구슬만 구멍을 만날 수도 있다.
4. . . .
[ 나는 바보였다 ] <- ?
왜 길찾기 문제가 백트래킹이라고 생각했지? 당연히 BFS 잖아 ;;;
요즘 계속 백트래킹만 풀어서 그런지 ..
덕분에 왜 길찾기 문제를 DFS로 풀면 안되는지 명확하게 이해했다 (!)
헛 고생만 몇 시간하다가 겨우 깨달았다 ^^
다음 코드는 정답 코드가 아닌,
백트래킹, 즉 DFS 로 풀다가 이전에 돌아온 경로를 저장하는 로직을 짜지 못한 코드입니다.
import java.io.*;
import java.util.*;
class Main {
public static int N = 0;
public static int M = 0;
public static String[][] MAP = null;
public static boolean[][] visited = null;
public static int[] dx = {1, -1, 0, 0}; // 상하좌우
public static int[] dy = {0, 0, -1, 1}; // 상하좌우
public static int MIN = Integer.MAX_VALUE;
public static int[] HOLE = null;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int[] nm = getIntArr(br.readLine().split(" "));
N = nm[0];
M = nm[1];
int[] red = null;
int[] blue = null;
MAP = new String[N][M];
visited = new boolean[N][M];
for (int i=0; i<N; i++) {
String[] line = br.readLine().split("");
for (int j=0; j<M; j++) {
MAP[i][j] = line[j];
switch (line[j]) {
case "R" -> {
red = new int[]{i, j};
MAP[i][j] = ".";
}
case "B" -> {
blue = new int[]{i, j};
MAP[i][j] = ".";
}
case "O" -> HOLE = new int[]{i, j};
}
}
}
// 시작점은 방문하고 시작.
visited[red[0]][red[1]] = true;
System.out.printf("초기RED[%d,%d] 초기BLUD[%d,%d]/n", red[0], red[1], blue[0], blue[1]);
backTracking(red[0], red[1], blue[0], blue[1], 0);
if (MIN > 10) System.out.println(-1);
else System.out.println(MIN);
}
/**
* 현재 지점에서, 구슬이 움직이는 중에 성공/실패를 판별 후에, 새로운 좌표를 재귀한다.
*/
public static void backTracking(int rx, int ry, int bx, int by, int count) {
System.out.println("count" + count);
// 만약 10번을 초과하여 움직였는데도 구멍에 도달하지 못했다면 실패.
if (count > 10) return;
// 상하좌우 중에 빨간 구슬이 이동할 곳이 있는가?
// 이때 MAP 의 가장자리에는 무조건 # 가 있기 때문에 범위가 벗어날 일은 없다.
for (int i = 0; i < 4; i ++) {
int new_rx = rx + dx[i];
int new_ry = ry + dy[i];
String direction = MAP[new_rx][new_ry];
if (!direction.equals("#")) { // 만족한다면 이동 가능. 벽만 아니면 된다.
// 구슬이 각자 굴러가는 경우
int movingRed = move(rx, ry, dx[i], dy[i]);
int movingBlue = move(bx, by, dx[i], dy[i]);
rx += dx[i] * movingRed;
ry += dy[i] * movingRed;
bx += dx[i] * movingBlue;
by += dy[i] * movingBlue;
System.out.printf("구슬이 굴러간 곳 RED[%d,%d] BLUE[%d,%d]/n", rx, ry, bx, by);
// 2. 구멍에 들어갈 수 있다.
if (MAP[rx + dx[i]][ry + dy[i]].equals("O")) {
System.out.println("빨간 구슬이 구멍에 들어갔습니다.");
// 만약 파란 구슬도 같이 들어갔다면..
if (MAP[bx + dx[i]][by + dy[i]].equals("O")) {
System.out.println("아.. 파란 구슬도 같이 들어갔네요.");
// [실패조건] 끝장이야 ...
return;
} else {
// [성공조건] 빨간 구슬만 구멍에 들어감.
MIN = Math.min(MIN, count + 1);
return;
}
}
// 가는 길목에서 만날 수 있는 경우
// 1. 굴러가다가 다른 구슬을 만날 수 있다. (같은 라인 구르기)
if (rx == bx && ry == by) { // 같은 좌표로 이동함.
if (movingRed > movingBlue) { // 파란 구슬이 앞에 있었음.
// 빨간 구슬 한 칸 뒤로.
rx -= dx[i];
rx -= dy[i];
}
else { // 빨간 구슬이 앞에 있었음.
// 파란 구슬 한 칸 뒤로.
bx -= dx[i];
by -= dy[i];
}
}
if (!visited[rx][ry]) {
visited[rx][ry] = true;
backTracking(rx, ry, bx, by, count + 1);
visited[rx][ry] = false;
}
// int crx = new_rx;
// int cry = new_ry;
//
// // 빨간 구슬이 이동한다.
// // 범위는 ? 벽을 만날 때까지.
// while (!MAP[crx][cry].equals("#")) {
// String current = MAP[crx][cry];
//
// // 어떤 구슬이 먼저 이동해야 하는가?
// // 빨간 구슬이 길목에 파란 구슬을 만난 즉시 파란 구슬을 먼저 이동시킨다.
// if (current.equals("B")) {
// int cbx = crx; // 파란 구슬 x 좌표
// int cby = cry; // 파란 구슬 y 좌표
//
// while(!MAP[cbx][cby].equals("#")) {
//
// // 파란 구슬이 굴러간다.
// cbx += dx[i];
// cby += dy[i];
// }
// }
//
// // 빨간 구슬이 굴러간다.
// crx += dx[i];
// cry += dy[i];
// }
//
// // 이동하는 도중에 구멍을 만날 것인가? [성공 조건]
// // 파란 구슬도 같이 만나면 안된다.
// if (isSuccess) return;
// else backTracking(crx - dx[i], crx - dx[i], c);
}
}
// 잠깐! 이때 이동하는 중에 `canMeetHole` 메소드를 소환해서 길목에 구멍이 있는지 확인
// 파란 공도 생각해야 한다. 파란공을 먼저 이동시키냐/빨간공을 먼저 이동시키냐...
// 이동하는 중에 일어날 수 있는
// 성공하지 못했을 시에 진정으로 새로운 좌표로 이동한다. 새 좌표로 backTracking 메소드 소환
}
public static int move(int x, int y, int dx, int dy) {
int count = 0;
x += dx;
y += dy;
while (MAP[x][y].equals(".")) {
count ++;
x += dx;
y += dy;
}
return count;
}
private static int[] getIntArr(String[] strArr) {
return Arrays.stream(strArr).mapToInt(Integer::parseInt).toArray();
}
}
※ 틀린 코드입니다 ※
(근데 이런 기록도 해놓긴 하고 싶었다,.. )
[ BFS 를 사용해서 다시 생각해보자 ]
import java.io.*;
import java.util.*;
class Main {
public static int N, M;
public static Character[][] MAP = null;
public static boolean[][][][] visited = null;
public static int[] dx = {-1, 1, 0, 0}; // 상하좌우
public static int[] dy = {0, 0, -1, 1}; // 상하좌우
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int[] nm = getIntArr(br.readLine().split(" "));
N = nm[0];
M = nm[1];
int[] red = new int[2];
int[] blue = new int[2];
MAP = new Character[N][M];
visited = new boolean[N][M][N][M];
for (int i = 0; i < N; i++) {
String line = br.readLine();
for (int j = 0; j < M; j++) {
MAP[i][j] = line.charAt(j);
if (MAP[i][j] == 'R') {
red[0] = i;
red[1] = j;
MAP[i][j] = '.';
} else if (MAP[i][j] == 'B') {
blue[0] = i;
blue[1] = j;
MAP[i][j] = '.';
}
}
}
ArrayDeque<int[]> q = new ArrayDeque<>();
q.add(new int[]{red[0], red[1], blue[0], blue[1], 0});
visited[red[0]][red[1]][blue[0]][blue[1]] = true;
while (!q.isEmpty()) {
int[] current = q.poll();
int rx = current[0];
int ry = current[1];
int bx = current[2];
int by = current[3];
int count = current[4];
if (count >= 10) {
System.out.println(-1);
return;
}
for (int i=0; i<4; i++) {
// Character direction = MAP[rx + dx[i]][ry + dy[i]];
// // 빨간 구슬이 이동 가능한 위치라면, 파란 구슬도 같이 움직인다.
// if (!direction.equals('#')) {
int[] movedRed = move(rx, ry, dx[i], dy[i]);
int[] movedBlue = move(bx, by, dx[i], dy[i]);
// 현재 빨간 구슬과 파란 구슬은 # 이나 O 앞에 있다.
// 파란 구슬이 구멍에 들어가면 실패
if (MAP[movedBlue[0]][movedBlue[1]] == 'O') continue;
// 빨간 구슬이 구멍에 들어가면 성공
if (MAP[movedRed[0]][movedRed[1]] == 'O') {
System.out.println(count + 1);
return;
}
// 두 구슬이 같은 위치에 있으면 이동 거리가 더 긴 구슬을 한 칸 뒤로
if (movedRed[0] == movedBlue[0] && movedRed[1] == movedBlue[1]) {
if (movedRed[2] > movedBlue[2]) {
movedRed[0] -= dx[i];
movedRed[1] -= dy[i];
} else {
movedBlue[0] -= dx[i];
movedBlue[1] -= dy[i];
}
}
// 방문하지 않은 상태라면 큐에 추가
if (!visited[movedRed[0]][movedRed[1]][movedBlue[0]][movedBlue[1]]) {
visited[movedRed[0]][movedRed[1]][movedBlue[0]][movedBlue[1]] = true;
q.offer(new int[]{movedRed[0], movedRed[1], movedBlue[0], movedBlue[1], count + 1});
}
// }
}
}
System.out.println(-1); // 모든 경우의 수를 탐색한 후에도 성공하지 못했을 경우
}
// 구슬을 벽이나 구멍을 만날 때까지 이동시키는 함수
public static int[] move(int x, int y, int dx, int dy) {
int dist = 0;
while (MAP[x + dx][y + dy] == '.' || MAP[x + dx][y + dy] == 'O') {
x += dx;
y += dy;
dist++;
if (MAP[x][y] == 'O') break; // 구슬이 구멍에 들어가면 즉시 멈춤
}
return new int[]{x, y, dist};
}
private static int[] getIntArr(String[] strArr) {
return Arrays.stream(strArr).mapToInt(Integer::parseInt).toArray();
}
}
정말... 정말정말.. 시간이 오래걸린 문제다
아직도 헷갈린다 ..
[ 깨달은 점 ]
동시에 움직여야 하는건.. 상태를 그냥 동시에 처리하도록 하자.
최솟 값 혹은 최단거리가 나올 때는 BFS 인지, Greedy 인지 잘 생각해보자.
'코딩테스트' 카테고리의 다른 글
| [백준 3190] 뱀 (Java, 골드4) (2) | 2024.10.16 |
|---|---|
| [백준 12100] 2048 (Easy) (Java, 골드1) (1) | 2024.10.12 |
| [백준 17136] 색종이 붙이기 (Java, 골드2) - 후속편 (2) | 2024.10.11 |
| [백준 1715] 카드 정렬하기 (Java, 골드4) (1) | 2024.10.11 |
| [백준 1026] 보물 (Java, 실버4) (0) | 2024.10.11 |