문제 링크입니다 https://www.acmicpc.net/problem/13460
13460번: 구슬 탈출 2
첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B' 로 이루어져 있다. '.'은 빈 칸을 의미하고, '#'은 공이 이동할 수 없는 장애물 또는 벽을 의미하며, 'O'는 구멍의 위치를 의미한다. 'R'은 빨간 구슬의 위치, 'B'는 파란 구슬의 위치이다. 입력되는 모든 보드
www.acmicpc.net
큐를 이용한 BFS를 통해 문제를 해결했습니다. 문제 해결 절차는 다음과 같습니다.
1. 빨간 구슬과 파란 구슬의 초기 위치의 좌표를 덩어리 채로 큐에 넣습니다.
2. 큐에서 꺼낸 빨간 구슬의 좌표는 구멍이고, 파란 구슬의 위치는 구멍이 아니면
→ 그 순간까지 구슬을 굴린 횟수를 정답으로 UPDATE 하고 BFS 함수를 종료합니다.
3. 2번의 경우가 아니면 각 구슬을 상, 하, 좌, 우 방향으로 움직이지 못할 때까지 굴려봅니다.
4. 굴러간 위치가 아직 방문하지 않은 좌표라면 덩어리 채로 큐에 넣고, 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
|
#include<algorithm>
#include<cstdio>
#include<queue>
using namespace std;
const int MAX = 10 + 10;
struct p {
int ry, rx, by, bx, count;
};
bool visit[MAX][MAX][MAX][MAX];
char map[MAX][MAX];
int n, m, ret;
p start;
const int dy[] = { -1, 1, 0, 0 };
const int dx[] = { 0, 0, -1, 1 };
p make_p(int ry, int rx, int by, int bx, int count) {
p temp;
temp.ry = ry, temp.rx = rx, temp.by = by, temp.bx = bx;
temp.count = count;
return temp;
}
int bfs(void) {
visit[start.ry][start.rx][start.by][start.bx] = true;
queue <p> q;
q.push(start);
int result = -1;
while (!q.empty()) {
p cur = q.front();
q.pop();
if (cur.count > 10) break;
if (map[cur.ry][cur.rx] == 'O' && map[cur.by][cur.bx] != 'O') {
result = cur.count;
break;
}
for (int i = 0; i < 4; i++) {
int ryy = cur.ry, rxx = cur.rx;
int byy = cur.by, bxx = cur.bx;
while (1) {
if (map[ryy][rxx] != '#' && map[ryy][rxx] != 'O')
ryy += dy[i], rxx += dx[i];
else {
if (map[ryy][rxx] == '#')
ryy -= dy[i], rxx -= dx[i];
break;
}
}
while (1) {
if (map[byy][bxx] != '#' && map[byy][bxx] != 'O')
byy += dy[i], bxx += dx[i];
else {
if (map[byy][bxx] == '#')
byy -= dy[i], bxx -= dx[i];
break;
}
}
if (ryy == byy && rxx == bxx) {
if (map[ryy][rxx] != 'O') {
int rdist = abs(ryy - cur.ry) + abs(rxx - cur.rx);
int bdist = abs(byy - cur.by) + abs(bxx - cur.bx);
if (rdist > bdist) ryy -= dy[i], rxx -= dx[i];
else byy -= dy[i], bxx -= dx[i];
}
}
if (!visit[ryy][rxx][byy][bxx]) {
visit[ryy][rxx][byy][bxx] = true;
q.push(make_p(ryy, rxx, byy, bxx, cur.count + 1));
}
}
}
return result;
}
void solve(void) {
scanf("%d%d", &n, &m);
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++) {
scanf(" %c", &map[i][j]);
if (map[i][j] == 'R')
start.ry = i, start.rx = j;
if (map[i][j] == 'B')
start.by = i, start.bx = j;
}
start.count = 0;
ret = bfs();
printf("%d", ret);
}
int main(void) {
solve();
return 0;
}
|
cs |
[소스코드 + 주석]
|
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
|
// [백준] 삼성 SW 역량 테스트 기출 문제 : 구슬 탈출 2(13460)
#include<algorithm>
#include<cstdio>
#include<queue>
using namespace std;
const int MAX = 10 + 10;
// 각 구슬의 좌표와 걸린 시간을 저장하기 위한 구조체
struct p {
int ry, rx, by, bx, count;
};
bool visit[MAX][MAX][MAX][MAX]; // 현재 덩어리의 방문 여부를 체크해줄 배열
char map[MAX][MAX];
int n, m, ret;
p start; // 각 구슬의 시작 좌표를 저장할 변수
const int dy[] = { -1, 1, 0, 0 };
const int dx[] = { 0, 0, -1, 1 };
// 각 구슬의 좌표와 걸린 시간을 인자로 받아 p type으로 바꿔주는 함수
p make_p(int ry, int rx, int by, int bx, int count) {
p temp;
temp.ry = ry, temp.rx = rx, temp.by = by, temp.bx = bx;
temp.count = count;
return temp;
}
// 각 구슬의 초기 위치를 시작으로 bfs를 통해 문제에서 요구하는 정답인 경우를 찾으면
// 그때까지 굴린 횟수를 반환하고 10번이 지나도 찾지 못하면 -1을 반환하는 함수
int bfs(void) {
// 초기 위치는 방문한 상태
visit[start.ry][start.rx][start.by][start.bx] = true;
queue <p> q;
q.push(start); // 큐에 초기 위치 push
int result = -1; // 정답인 경우를 찾지 못하면 초기값 -1을 반환
while (!q.empty()) {
p cur = q.front();
q.pop();
if (cur.count > 10) break; // 굴린 횟수가 10번이 넘으면 그냥 break
// 정답인 경우(빨간 구슬은 구멍에 파란 구슬은 노구멍)를 찾았습니다!
if (map[cur.ry][cur.rx] == 'O' && map[cur.by][cur.bx] != 'O') {
result = cur.count; // 정답을 현재 횟수로 update
break;
}
for (int i = 0; i < 4; i++) {
int ryy = cur.ry, rxx = cur.rx; // 빨간 구슬의 다음 좌표를 저장할 변수
int byy = cur.by, bxx = cur.bx; // 파란 구슬의 다음 좌표를 저장할 변수
// 빨간 구슬부터 굴립니다
while (1) {
// 현재 칸이 벽이 아니고, 구멍이 아니라면 한 칸 갑니다
if (map[ryy][rxx] != '#' && map[ryy][rxx] != 'O')
ryy += dy[i], rxx += dx[i];
else {
// 현재 칸이 벽이거나 구멍인데 벽일 땐 한칸 뒤로 가줍니다
if (map[ryy][rxx] == '#')
ryy -= dy[i], rxx -= dx[i];
break;
}
}
// 파란 구슬을 동일하게 굴립니다
while (1) {
if (map[byy][bxx] != '#' && map[byy][bxx] != 'O')
byy += dy[i], bxx += dx[i];
else {
if (map[byy][bxx] == '#')
byy -= dy[i], bxx -= dx[i];
break;
}
}
// 굴리고 났더니 빨간 구슬과 파란 구슬의 위치가 동일하다면
if (ryy == byy && rxx == bxx) {
// 만약 위치가 동일하고 그 위치의 빨간 구슬이 구멍이라면
// 정답이거나 혹은 둘 다 구멍인 무시해도 되는 경우이므로
// 빨간 구슬의 위치가 구멍이 아닌 경우에만
if (map[ryy][rxx] != 'O') {
// 둘 중에 많이 굴러온 놈을 한 칸 뒤로 보냅니다
int rdist = abs(ryy - cur.ry) + abs(rxx - cur.rx);
int bdist = abs(byy - cur.by) + abs(bxx - cur.bx);
if (rdist > bdist) ryy -= dy[i], rxx -= dx[i];
else byy -= dy[i], bxx -= dx[i];
}
}
// 결정된 두 구슬의 다음 위치를 아직 방문하지 않았다면 큐에 push
if (!visit[ryy][rxx][byy][bxx]) {
visit[ryy][rxx][byy][bxx] = true;
q.push(make_p(ryy, rxx, byy, bxx, cur.count + 1));
}
}
}
return result;
}
void solve(void) {
scanf("%d%d", &n, &m);
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++) {
scanf(" %c", &map[i][j]);
if (map[i][j] == 'R')
start.ry = i, start.rx = j;
if (map[i][j] == 'B')
start.by = i, start.bx = j;
}
start.count = 0;
ret = bfs();
printf("%d", ret);
}
int main(void) {
solve();
return 0;
}
|
cs |
'알고리즘 > BaekJoon' 카테고리의 다른 글
| 백준 1051 : 숫자 정사각형 (0) | 2020.02.21 |
|---|---|
| 백준 10448 : 유레카 이론 (0) | 2020.02.21 |
| 백준 3190 : 뱀 (0) | 2020.02.20 |
| 백준 14888 : 연산자 끼워넣기 (0) | 2020.02.20 |
| 백준 14501 : 퇴사 (0) | 2020.02.20 |