Algorithm 문제
[백준] 13460 - 구슬 탈출 2
노예2
2019. 7. 13. 01:35
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
브루트포스로 해결할 수 있는 문제
문제 자체는 간단하나 조건이 많아 구현 과정에서 실수가 발생할 확률이 높은 문제.
틀렸을 경우에는 빠진 조건이 없는지 다시 한 번 읽어보자.
개인적으로는 코드가 길어지더라도 명확하게 작성하는 것이 오류를 찾는 것에 도움이 된다.
구슬의 충돌은 어떤 순서로 구슬을 움직이냐에 따라 발생 할 수도, 안 할 수도 있으므로 번갈아가며 2회 움직여 해결하였다.
혹시 틀렸을 경우 아래 블로그에 test case를 100개 작성해 놓으신 분께 감사하며 정답을 확인해보자.
https://boohyunsik.github.io/exit-marble-test-case/
백준) 구슬 탈출2 TC
구슬 탈출2 문제의 Test case
boohyunsik.github.io
<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
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
|
#include <cstdio>
#include <queue>
#include <algorithm>
using namespace std;
// 현재 상태를 저장하는 구조체 (회전 횟수, 붉은 공 위치, 푸른 공 위치)
struct stat{
int num;
pair<int, int> r;
pair<int, int> b;
};
int main(){
int n, m;
pair<int, int> r, b, h;
char board[11][11] = {};
int dy[4] = {-1, 0, 1, 0}, dx[4] = {0, -1, 0, 1};
// 인덱스는 순서대로 red y, red x, blue y, blue x
bool vis[11][11][11][11] = {};
scanf("%d %d", &n, &m);
for(int i=0; i<n; i++){
scanf("%s", &board[i]);
for(int j=0; j<m; j++){
if(board[i][j] == 'B') b = make_pair(i, j);
else if(board[i][j] == 'R') r = make_pair(i, j);
}
}
// bfs
queue<stat> q;
// 초기값 설정
stat start = {0, r, b};
vis[start.r.first][start.r.second][start.b.first][start.b.second] = true;
q.push(start);
// 순회
while(!q.empty()){
// 각 방향 순회
for(int d=0; d<4; d++){
stat tmp = q.front();
bool collision_red = false, collision_blue = false;
bool red_in = false, blue_in = false;
// r 먼저 이동
while(true){
int ay = tmp.r.first + dy[d];
int ax = tmp.r.second + dx[d];
// 벽 만날 시 이동 종료
if(board[ay][ax] == '#'){
break;
}
// 파란공과 충돌 시, 나중에 다시 이동
else if(ay == tmp.b.first && ax == tmp.b.second){
collision_red = true;
break;
}
// 구멍 들어갈 시, 표시
else if(board[ay][ax] == 'O'){
tmp.r.first = -1;
red_in = true;
break;
}
tmp.r.first += dy[d];
tmp.r.second += dx[d];
}
// b 이동
while(true){
int ay = tmp.b.first + dy[d];
int ax = tmp.b.second + dx[d];
// 벽 만날 시 이동 종료
if(board[ay][ax] == '#'){
break;
}
// 빨간공과 충돌 시, 나중에 다시 이동
else if(ay == tmp.r.first && ax == tmp.r.second){
collision_blue;
break;
}
// 구멍 들어갈 시, 실패
else if(board[ay][ax] == 'O'){
blue_in = true;
break;
}
tmp.b.first += dy[d];
tmp.b.second += dx[d];
}
// r 이 b에 걸려서 멈출 시, r 다시 이동
while(collision_red){
int ay = tmp.r.first + dy[d];
int ax = tmp.r.second + dx[d];
// 벽 만날 시 이동 종료
if(board[ay][ax] == '#'){
break;
}
// 파란공과 충돌 시, 정지
else if(ay == tmp.b.first && ax == tmp.b.second){
break;
}
// 구멍 들어갈 시, 프로그램 종료
else if(board[ay][ax] == 'O'){
tmp.r.first = -1;
red_in = true;
break;
}
tmp.r.first += dy[d];
tmp.r.second += dx[d];
}
// b 다시 이동
while(collision_blue){
int ay = tmp.b.first + dy[d];
int ax = tmp.b.second + dx[d];
// 벽 만날 시 이동 종료
if(board[ay][ax] == '#'){
break;
}
// 빨간공과 충돌 시, 나중에 다시 이동
else if(ay == tmp.r.first && ax == tmp.r.second){
break;
}
// 구멍 들어갈 시, 실패
else if(board[ay][ax] == 'O'){
blue_in = true;
break;
}
tmp.b.first += dy[d];
tmp.b.second += dx[d];
}
if(blue_in){
continue;
}
if(red_in){
printf("%d", tmp.num + 1);
return 0;
}
if(!vis[tmp.r.first][tmp.r.second][tmp.b.first][tmp.b.second]){
vis[tmp.r.first][tmp.r.second][tmp.b.first][tmp.b.second] = true;
stat new_stat = {tmp.num + 1, tmp.r, tmp.b};
q.push(new_stat);
}
}
stat tmp = q.front();
if(tmp.num > 9){
break;
}
q.pop();
}
// 10회 이내에 해결 불가능
printf("-1");
return 0;
}
|
cs |