백준 13460번 : 구슬 이동 2
이번 문제는 4 문제까지 있는 구슬 탈출 문제 중 두 번째 문제이다.
n*m 크기의 보드가 주어지고, 이 보드에서 구슬을 상하좌우로 굴렸을 때 구멍에 도달할 수 있는 횟수를 리턴하는 문제이다.
구슬 굴리기는 중력의 힘을 사용하기 때문에 벽인 #에서 멈출 수 밖에 없다.
또한, 구슬의 종류가 빨강과 파랑 두 가지인데, 문제에서는 빨강이 구멍에 도달해야하고 파랑이 구멍에 도달하게 되면 실패로 취급해 -1을 리턴해야한다.
빨강이 먼저 구멍에 도달하고, 연이어 파랑도 도달하게 된다면 실패이다.
그래프는 ‘.’,’#’,’O’,’R’,’B’ 로 이루어져 있다.
각각 ‘.’은 빈칸, ‘#’은 벽, ‘O’는 구멍, ‘R’과 ‘B’는 각각 빨간 구슬, 파란 구슬을 의미한다.
도착지인 구멍, 구슬 두 종류는 항상 1개만 주어진다.
우선 이 문제를 최대한 풀어보려고 했는데, 방문 체크의 위치를 못 잡고 헤맸고, 구슬 이동에 대한 처리가 어려웠다.
결국 아래 블로그를 참고했다.
✧˖˚˳⊹ 안 까먹을려고 ˚₊‧♡ ੈ - [백준 - Java] 13460번 : 구슬 탈출 2
참고 전 기존 코드는 다음과 같다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
static int n, m;
static char[][] map;
static boolean[][][][] visited;
static int[] dx = {-1, 1, 0, 0}, dy = {0, 0, -1, 1};
static int rx, ry, bx, by, holeX, holeY;
public static void main(String[] args) throws java.io.IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
n = Integer.parseInt(st.nextToken());
m = Integer.parseInt(st.nextToken());
map = new char[n][m];
visited = new boolean[n][m][n][m];
for (int i = 0; i < n; i++) {
String str = br.readLine();
for (int j = 0; j < m; j++) {
map[i][j] = str.charAt(j);
if (map[i][j] == 'R') {
rx = i;
ry = j;
} else if (map[i][j] == 'B') {
bx = i;
by = j;
} else if (map[i][j] == 'O') {
holeX = i;
holeY = j;
}
}
}
System.out.println(bfs());
}
static int bfs() {
Queue<int[]> q = new LinkedList<>();
q.add(new int[]{rx, ry, bx, by, 0});
visited[rx][ry][bx][by] = true;
while (!q.isEmpty()) {
int[] current = q.poll();
int curRx = current[0];
int curRy = current[1];
int curBx = current[2];
int curBy = current[3];
int count = current[4];
if (count > 10) return -1;
for (int i = 0; i < 4; i++) {
int[] nextR, nextB;
if ((i == 0 && curRx < curBx) || (i == 1 && curRx > curBx) || (i == 2 && curRy < curBy) || (i == 3 && curRy > curBy)) {
nextR = move(curRx, curRy, dx[i], dy[i]);
nextB = move(curBx, curBy, dx[i], dy[i]);
} else {
nextB = move(curBx, curBy, dx[i], dy[i]);
nextR = move(curRx, curRy, dx[i], dy[i]);
}
if(nextB[0] == holeX && nextB[1] == holeY) continue;
if (nextR[0] == holeX && nextR[1] == holeY) return count + 1;
if (nextR[0] == nextB[0] && nextR[1] == nextB[1]) {
if (nextR[2] > nextB[2]) {
nextR[0] -= dx[i];
nextR[1] -= dy[i];
} else {
nextB[0] -= dx[i];
nextB[1] -= dy[i];
}
}
if (!visited[nextR[0]][nextR[1]][nextB[0]][nextB[1]]) {
visited[nextR[0]][nextR[1]][nextB[0]][nextB[1]] = true;
q.add(new int[]{nextR[0], nextR[1], nextB[0], nextB[1], count + 1});
}
}
}
return -1;
}
static int[] move(int x, int y, int dx, int dy) {
int count = 0;
while (true) {
x += dx;
y += dy;
count++;
if(map[x][y] == '#') {
x -= dx;
y -= dy;
count--;
break;
}
if(map[x][y] == 'O') break;
}
return new int[]{x, y, count};
}
}
블로그에서 참고한 코드와의 다른 점은 다음과 같다.
- 정답 소스 코드에서는 Marble 클래스 사용으로 R과 B의 위치 정보와 이동 횟수를 한번에 관리한다.
- 정답 소스 코드에서는 방문 체크를 더 일찍 하고 있다. 기존 풀이에서는 방문 체크를 구슬이 이동한 후에 하고 있는데, 이 경우 중복 방문을 방지할 수 없다.
- 기존 풀이에서는 빨간 구슬이 먼저 이동하게 하고, 그 다음에 파란 구슬이 이동하게 한다. 반면, 정답 소스 코드에서는 두 구슬이 동시에 이동한다. 이 때문에 이동 거리가 더 긴 구슬을 한 칸 뒤로 이동시켰다. 이는, 두 구슬이 같은 위치에 도달하는 경우를 처리하는 것이다.
정리하면, 방문 체크 실행 위치와 구슬 이동 순서 처리에 대한 차이 때문에 기존 풀이가 계속 오답 처리가 되었던 것이다.
이제 블로그에서 참고한 코드를 자세히 살펴보자.
문제를 풀기 위해 선언된 멤버 변수는 다음과 같다.
1
2
3
4
5
6
7
public class Main {
static int n, m;
static char[][] map;
static boolean[][][][] visited; // 적구, 청구 2개 -> 각 x,y 좌표 방문 여부
static int holeX, holeY;
static Marble blue, red;
static int[] dx = {-1, 0, 1, 0}, dy = {0, 1, 0, -1};
n과 m은 그래프의 크기이고, map은 해당 그래프를 나타낸다.
또한 여기서 visited 배열이 4차원으로 무시무시한데, 주석에 써놓았듯이 1차원부터 각각 빨간 구슬의 x,y 좌표, 파란 구슬의 x,y 좌표를 의미한다.
여기서부터 지대하게 헷갈릴 것이다.
hole x,y는 단어 그대로 구멍의 x,y 좌표를 뜻한다.
marble은 추후 설명할 빨간 구슬, 파란 구슬의 좌표와 이동 거리를 가지고 있는 정적 클래스이다.
dx,dy는 상하좌우 이동을 의미한다.
marble 이너 클래스는 다음과 같다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
static class Marble {
// 레드
int rx;
int ry;
// 블루
int bx;
int by;
// 이동
int cnt;
public Marble(int rx, int ry, int bx, int by, int cnt) {
this.rx = rx;
this.ry = ry;
this.bx = bx;
this.by = by;
this.cnt = cnt;
}
}
이 marble 클래스는 빨간 구슬과 파란 구슬의 위치와 이동 횟수를 저장하는 데에 사용된다.
rx, ry는 빨간 구슬의 위치를 나타내고, bx, by는 파란 구슬의 위치를 나타낸다.
cnt는 이동 횟수를 저장하는 변수이다.
이 클래스에는 생성자가 하나 있으며, 이 생성자는 빨간 구슬의 위치, 파란 구슬의 위치, 이동 횟수를 인자로 받아 각 필드에 저장하게된다.
이를 통해 구슬의 위치 정보, 그리고 이동 횟수를 한번에 저장 후 활용할 수 있어, 코드의 가독성을 높이고 복잡도를 줄일 수 있다.
다음으로는 main 함수에서의 그래프 생성을 볼 것이다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
public static void main(String[] args) throws java.io.IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
n = Integer.parseInt(st.nextToken());
m = Integer.parseInt(st.nextToken());
map = new char[n][m];
visited = new boolean[n][m][n][m];
for (int i = 0; i < n; i++) {
String str = br.readLine();
for (int j = 0; j < m; j++) {
map[i][j] = str.charAt(j);
if(map[i][j] == 'O') {
holeX = i;
holeY = j;
} else if(map[i][j] == 'B') {
blue = new Marble(0, 0, i, j, 0);
} else if(map[i][j] == 'R') {
red = new Marble(i, j, 0, 0, 0);
}
}
}
System.out.println(bfs());
}
앞선 입력에 관해서는 생략한다.
입력되는 그래프를 생성함과 동시에 구멍의 x,y 좌표와 각 구슬의 좌표를 저장한다.
그 다음으로는 bfs를 실행하여 이동 횟수를 리턴하면 된다.
BFS 탐색은 다음과 같은 로직이다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
public static int bfs() {
Queue<Marble> q = new LinkedList<>();
q.offer(new Marble(red.rx, red.ry, blue.bx, blue.by, 1));
visited[red.rx][red.ry][blue.rx][blue.ry] = true;
while(!q.isEmpty()) {
Marble marble = q.poll();
int curRx = marble.rx;
int curRy = marble.ry;
int curBx = marble.bx;
int curBy = marble.by;
int curCnt = marble.cnt;
// 조건 : 이동 횟수 10회 미만
if (curCnt > 10) {
return -1;
}
for (int i = 0; i < 4; i++) {
int newRx = curRx;
int newRy = curRy;
int newBx = curBx;
int newBy = curBy;
boolean isRed = false;
boolean isBlue = false;
// 적구 이동
while (map[newRx + dx[i]][newRy + dy[i]] != '#') {
newRx += dx[i];
newRy += dy[i];
// 구멍 도달
if (newRx == holeX && newRy == holeY) {
isRed = true;
break;
}
}
// 청구 이동
while(map[newBx + dx[i]][newBy + dy[i]] != '#') {
newBx += dx[i];
newBy += dy[i];
// 구멍 도달
if (newBx == holeX && newBy == holeY) {
isBlue = true;
break;
}
}
if (isBlue) { // 청구 구멍 도달 시 실패
continue; // 다른 경우의 수로
}
if (isRed && !isBlue) { // 무조건 성공 분기
return curCnt;
}
// 두 구슬이 구멍 도달 X 이동 위치가 같은 경우 조정
if (newRx == newBx && newRy == newBy) {
if (i == 0) { // 위
// 더 큰 x값을 가지는 구슬이 뒤로
if (curRx > curBx) newRx -= dx[i];
else newBx -= dx[i];
} else if (i == 1) { // 우
// 더 작은 y값을 가지는 구슬이 뒤로
if (curRy < curBy) newRy -= dy[i];
else newBy -= dy[i];
} else if (i == 2) { // 하
// 더 작은 x값을 가지는 구슬이 뒤로
if (curRx < curBx) newRx -= dx[i];
else newBx -= dx[i];
} else { // 좌
// 더 큰 y값을 가지는 구슬이 뒤로
if (curRy > curBy) newRy -= dy[i];
else newBy -= dy[i];
}
}
// 두 구슬이 이동할 위치가 방문하지 않았던 곳인 경우 이동
if (!visited[newRx][newRy][newBx][newBy]) {
visited[newRx][newRy][newBx][newBy] = true;
q.offer(new Marble(newRx, newRy, newBx, newBy, curCnt + 1));
}
}
}
return -1;
}
우선 이 탐색법은 최소 이동 횟수를 리턴해야하는 문제에 맞춰 작성되었는데, 상당히 길어 복잡할 수 있다.
그렇기 때문에 순서대로 살펴볼 것이다.
우선 여타 BFS 문제와 마찬가지로 큐를 생성하고 빨간 구슬과 파란 구슬의 시작 위치를 큐에 넣는다.
동시에 넣어주기 때문에 이 큐는 Marble 타입을 참조하는 것이다.
또한 해당 위치의 중복 탐색을 방지하기 위해 방문 여부를 true로 변경해준다.
BFS 실행 시 흐름은 다음과 같다.
- 큐에서 구슬 정보를 꺼낸다.
- 이동 횟수가 10을 초과하면 무조건 실패로 간주해야하기 때문에 -1을 반환한다.
- 4가지 방향에 대해 구슬을 이동시킨다. 이때, 빨간 구슬과 파란 구슬이 동시에 이동하며, 벽에 도달하거나 구멍에 빠질 때까지 이동시킨다.
- 파란 구슬이 구멍에 빠졌다면, 이 경우는 실패한 경우이다. 탐색을 종료하고 다음 경우를 찾는다.
- 빨간 구슬만 구멍에 빠졌다면, 이 경우는 성공한 경우이다. 이동 횟수를 반환한다.
- 두 구슬이 모두 구멍에 빠지지 않았고 이동한 위치가 같은 경우, 이동하기 전의 위치를 비교하여 이동 거리가 더 긴 구슬을 한 칸 뒤로 옮긴다.
- 이동 후의 위치를 방문하지 않았다면, 이 위치를 방문했다고 표시하고 이 위치와 이동 횟수를 큐에 넣어 다음에 확인하도록 한다.
이후 모든 경우의 수를 탐색 했는데, 큐가 비어있음에도 빨간 구슬이 구멍에 빠지지 않았다면 실패로 간주하고 -1을 반환하게 된다.
위와 같은 흐름을 통해 정답에 도달할 수 있다.
전체 소스 코드는 다음과 같다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
static int n, m;
static char[][] map;
static boolean[][][][] visited; // 적구, 청구 2개 -> 각 x,y 좌표 방문 여부
static int holeX, holeY;
static Marble blue, red;
static int[] dx = {-1, 0, 1, 0}, dy = {0, 1, 0, -1};
static class Marble {
// 레드
int rx;
int ry;
// 블루
int bx;
int by;
// 이동
int cnt;
public Marble(int rx, int ry, int bx, int by, int cnt) {
this.rx = rx;
this.ry = ry;
this.bx = bx;
this.by = by;
this.cnt = cnt;
}
}
public static void main(String[] args) throws java.io.IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
n = Integer.parseInt(st.nextToken());
m = Integer.parseInt(st.nextToken());
map = new char[n][m];
visited = new boolean[n][m][n][m];
for (int i = 0; i < n; i++) {
String str = br.readLine();
for (int j = 0; j < m; j++) {
map[i][j] = str.charAt(j);
if(map[i][j] == 'O') {
holeX = i;
holeY = j;
} else if(map[i][j] == 'B') {
blue = new Marble(0, 0, i, j, 0);
} else if(map[i][j] == 'R') {
red = new Marble(i, j, 0, 0, 0);
}
}
}
System.out.println(bfs());
}
public static int bfs() {
Queue<Marble> q = new LinkedList<>();
q.offer(new Marble(red.rx, red.ry, blue.bx, blue.by, 1));
visited[red.rx][red.ry][blue.rx][blue.ry] = true;
while(!q.isEmpty()) {
Marble marble = q.poll();
int curRx = marble.rx;
int curRy = marble.ry;
int curBx = marble.bx;
int curBy = marble.by;
int curCnt = marble.cnt;
// 조건 : 이동 횟수 10회 미만
if (curCnt > 10) {
return -1;
}
for (int i = 0; i < 4; i++) {
int newRx = curRx;
int newRy = curRy;
int newBx = curBx;
int newBy = curBy;
boolean isRed = false;
boolean isBlue = false;
// 적구 이동
while (map[newRx + dx[i]][newRy + dy[i]] != '#') {
newRx += dx[i];
newRy += dy[i];
// 구멍 도달
if (newRx == holeX && newRy == holeY) {
isRed = true;
break;
}
}
// 청구 이동
while(map[newBx + dx[i]][newBy + dy[i]] != '#') {
newBx += dx[i];
newBy += dy[i];
// 구멍 도달
if (newBx == holeX && newBy == holeY) {
isBlue = true;
break;
}
}
if (isBlue) { // 청구 구멍 도달 시 실패
continue; // 다른 경우의 수로
}
if (isRed && !isBlue) { // 무조건 성공 분기
return curCnt;
}
// 두 구슬이 구멍 도달 X 이동 위치가 같은 경우 조정
if (newRx == newBx && newRy == newBy) {
if (i == 0) { // 위
// 더 큰 x값을 가지는 구슬이 뒤로
if (curRx > curBx) newRx -= dx[i];
else newBx -= dx[i];
} else if (i == 1) { // 우
// 더 작은 y값을 가지는 구슬이 뒤로
if (curRy < curBy) newRy -= dy[i];
else newBy -= dy[i];
} else if (i == 2) { // 하
// 더 작은 x값을 가지는 구슬이 뒤로
if (curRx < curBx) newRx -= dx[i];
else newBx -= dx[i];
} else { // 좌
// 더 큰 y값을 가지는 구슬이 뒤로
if (curRy > curBy) newRy -= dy[i];
else newBy -= dy[i];
}
}
// 두 구슬이 이동할 위치가 방문하지 않았던 곳인 경우 이동
if (!visited[newRx][newRy][newBx][newBy]) {
visited[newRx][newRy][newBx][newBy] = true;
q.offer(new Marble(newRx, newRy, newBx, newBy, curCnt + 1));
}
}
}
return -1;
}
}
와우. 코드가 엄청 길다.
그리고 처음 접했을 때 이걸 어떻게 나눠서 풀어야되는지 진짜 하나도 감이 안 왔었다.
결국 참고를 했지만 이 마저도 완벽하지 않다.
그래도 기억하기 위해 기록은 했다.
문제의 난이도가 골드 1이라는데, 아직 여전히 골드 상위 문제는 스스로 전부 풀어내지는 못하는 것 같다.
너무 어려웠다…
이 블로그는 저작권자의 CC BY 4.0 라이센스를 따릅니다.