15653번: 구슬 탈출 4
첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B'
www.acmicpc.net
보드를 4방향으로 기울여 구슬을 구멍으로 빼내는데 걸리는 최소 횟수를 출력하는 문제입니다. 구멍을 통해 빼낼 수 없으면 -1을 출력합니다.
시뮬레이션으로 구슬을 이동시켜야하며, 4방향으로 기울이는 것은 bfs를 이용하였습니다.
우선 큐에 입력으로 받은 빨간 구슬의 좌표, 파란 구슬의 좌표, 그리고 0(움직인 횟수)를 넣습니다.
그 다음 bfs로 구슬을 움직여줍니다.
구슬을 움직일 때는
1. 빨간 구슬과 파란 구슬을 벽이나 구멍이 있을때까지 움직여줍니다.
2. 만약 파란 구슬이 도중에 탈출했다면 continue (파란 구슬은 탈출하면 안됩니다.)
3. 파란 구슬이 탈출 안했고, 빨간 구슬이 탈출 했으면 cnt + 1 출력
4. 둘 다 탈출 못했으면 큐에 넣기 전에 구슬들이 겹칠 가능성이 존재하므로 확인해줍니다.
5. 구슬들이 겹쳐있으면 원래의 자리와 거리를 구해 먼 쪽이 한칸 뒤로 이동합니다.
6. 이제 다음 칸인 (nrx, nry), (nbx, nby)의 방문했는지 확인해줍니다.
7. 모두 통과되면 방문 체크를 해주고, 큐에 넣어줍니다.
8. 만약 큐가 비어있게 되면 탈출을 못했다는 뜻이므로 -1을 출력해줍니다.
백준에 있는 구슬 탈출 문제가 여러개 있는데 똑같은 문제인것 같네요
[C++]
|
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
|
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
typedef struct point {
int rx;
int ry;
int bx;
int by;
int cnt;
}point;
queue<point> q;
bool visit[11][11][11][11];
char list[11][11];
int direct[4][2] = { {0,1},{1,0},{0,-1},{-1,0} };
int N, M;
void bfs() {
while (!q.empty()) {
int rx = q.front().rx;
int ry = q.front().ry;
int bx = q.front().bx;
int by = q.front().by;
int cnt = q.front().cnt;
q.pop();
for (int i = 0; i < 4; i++) {
int nrx = rx;
int nry = ry;
bool redchk = false;
bool bluechk = false;
while (1) {
nrx += direct[i][0];
nry += direct[i][1];
if (list[nrx][nry] == '#') {
nrx -= direct[i][0];
nry -= direct[i][1];
break;
}
else if (list[nrx][nry] == 'O') {
redchk = true;
break;
}
}
int nbx = bx;
int nby = by;
while (1) {
nbx += direct[i][0];
nby += direct[i][1];
if (list[nbx][nby] == '#') {
nbx -= direct[i][0];
nby -= direct[i][1];
break;
}
else if (list[nbx][nby] == 'O') {
bluechk = true;
break;
}
}
if (bluechk) continue;
else if (redchk) {
cout << cnt + 1 << '\n';
return;
}
if (nrx == nbx && nry == nby) {
int reddis = abs(nrx - rx) + abs(nry - ry);
int bluedis = abs(nbx - bx) + abs(nby - by);
if (reddis > bluedis) {
nrx -= direct[i][0];
nry -= direct[i][1];
}
else {
nbx -= direct[i][0];
nby -= direct[i][1];
}
}
if (visit[nrx][nry][nbx][nby]) continue;
q.push({ nrx,nry,nbx,nby,cnt + 1 });
visit[nrx][nry][nbx][nby] = true;
}
}
cout << "-1\n";
}
void input() {
int rx, ry, bx, by;
cin >> N >> M;
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
cin >> list[i][j];
if (list[i][j] == 'B') {
bx = i;
by = j;
}
else if (list[i][j] == 'R') {
rx = i;
ry = j;
}
}
}
q.push({ rx,ry,bx,by,0 });
visit[rx][ry][bx][by] = true;
}
int main() {
cin.tie(NULL); cout.tie(NULL);
ios::sync_with_stdio(false);
input();
bfs();
return 0;
}
|
cs |
[Java]
|
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
|
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.StringTokenizer;
public class Main {
static class Pair {
int rx;
int ry;
int bx;
int by;
int cnt;
public Pair(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;
}
}
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static StringTokenizer st;
static Deque<Pair> dq = new ArrayDeque<>();
static boolean visit[][][][] = new boolean[11][11][11][11];
static char list[][] = new char[11][11];
static int direct[][] = { { 0, 1 }, { 1, 0 }, { 0, -1 }, { -1, 0 } };
static int N, M;
static void bfs() {
while (!dq.isEmpty()) {
int rx = dq.peek().rx;
int ry = dq.peek().ry;
int bx = dq.peek().bx;
int by = dq.peek().by;
int cnt = dq.poll().cnt;
for (int i = 0; i < 4; i++) {
int nrx = rx;
int nry = ry;
boolean redchk = false;
while (true) {
nrx += direct[i][0];
nry += direct[i][1];
if (list[nrx][nry] == '#') {
nrx -= direct[i][0];
nry -= direct[i][1];
break;
}
if (list[nrx][nry] == 'O') {
redchk = true;
break;
}
}
int nbx = bx;
int nby = by;
boolean bluechk = false;
while (true) {
nbx += direct[i][0];
nby += direct[i][1];
if (list[nbx][nby] == '#') {
nbx -= direct[i][0];
nby -= direct[i][1];
break;
}
if (list[nbx][nby] == 'O') {
bluechk = true;
break;
}
}
if (bluechk)
continue;
else if (redchk) {
System.out.println(cnt + 1);
return;
}
if (nrx == nbx && nry == nby) {
int reddis = Math.abs(nrx - rx) + Math.abs(nry - ry);
int bluedis = Math.abs(nbx - bx) + Math.abs(nby - by);
if (bluedis < reddis) {
nrx -= direct[i][0];
nry -= direct[i][1];
} else {
nbx -= direct[i][0];
nby -= direct[i][1];
}
}
if (visit[nrx][nry][nbx][nby])
continue;
dq.add(new Pair(nrx, nry, nbx, nby, cnt + 1));
visit[nrx][nry][nbx][nby] = true;
}
}
System.out.println(-1);
}
static void input() throws Exception {
int rx = 0, ry = 0, bx = 0, by = 0;
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
list[i] = st.nextToken().toCharArray();
for (int j = 0; j < M; j++) {
if (list[i][j] == 'R') {
rx = i;
ry = j;
} else if (list[i][j] == 'B') {
bx = i;
by = j;
}
}
}
dq.add(new Pair(rx, ry, bx, by, 0));
visit[rx][ry][bx][by] = true;
}
public static void main(String[] args) throws Exception {
input();
bfs();
}
}
|
cs |
'algorithm > bfs' 카테고리의 다른 글
| boj 2589 보물섬 (0) | 2021.03.16 |
|---|---|
| boj 11559 Puyo Puyo (0) | 2021.02.26 |
| boj 1525 퍼즐 (0) | 2021.02.19 |
| boj 7576 토마토 (0) | 2021.02.19 |
| boj 17135 캐슬 디펜스 (0) | 2021.02.17 |