반응형
13460번: 구슬 탈출 2
첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B'
www.acmicpc.net
알고리즘 종류
구현
BFS
사고 과정
BFS를 이용해서 각 구슬의 위치를 저장하여 해결했습니다. 동일한 위치로 갈 수 있기 때문에 4차원 배열 isVisited를 생성하여 재방문을 체크했습니다.
1. 파란 구슬과 빨간 구슬을 움직입니다. 움직이는 도중에 구멍을 지나면 체크해 줍니다.
2. 파란 구슬이 빠졌으면 continue 합니다. 빨간 구슬만 빠졌으면 종료합니다.
3. 구슬이 겹치는 경우가 있습니다. 움직이지 전의 위치를 기준으로 어느 구슬이 뒤에 있는지 확인해서 한 칸 뒤로 옮깁니다.
4. 재방문을 확인하고 queue에 넣습니다.
구현(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
|
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
struct State{
int by;
int bx;
int ry;
int rx;
};
int h, w;
int by, bx, ry, rx;
char mat[11][11];
int dir[4][2] = {{1,0}, {0,1}, {-1,0}, {0,-1}};
int isVisited[11][11][11][11]; // by, bx, ry, rx로 재방문 방지
void solution(){
queue<State> q;
q.push({by, bx, ry, rx});
isVisited[by][bx][ry][rx] = 1;
int ans = 1;
while(!q.empty()){
if(ans > 10){
cout << -1 << endl;
return;
}
int size = q.size();
while(size--){
by = q.front().by;
bx = q.front().bx;
ry = q.front().ry;
rx = q.front().rx;
q.pop();
for(int d=0; d<4; d++){
int nby = by;
int nbx = bx;
int nry = ry;
int nrx = rx;
bool flag_red = false;
bool flag_blue = false;
// blue move
while(true){
nby += dir[d][0];
nbx += dir[d][1];
if(mat[nby][nbx] == 'O') flag_blue = true;
if(mat[nby][nbx] == '#'){
nby -= dir[d][0];
nbx -= dir[d][1];
break;
}
}
// red move
while(true){
nry += dir[d][0];
nrx += dir[d][1];
if(mat[nry][nrx] == 'O') flag_red = true;
if(mat[nry][nrx] == '#'){
nry -= dir[d][0];
nrx -= dir[d][1];
break;
}
}
if(flag_blue) continue;
if(flag_red && !flag_blue){
cout << ans << endl;
return;
}
// overlapped
if(nby==nry && nbx==nrx){
// same row
if(by==ry){
if(d==1){
if(bx<rx) nbx -= 1;
else nrx -= 1;
}
else if(d==3){
if(bx>rx) nbx += 1;
else nrx += 1;
}
}
// same column
else if(bx==rx){
if(d==0){
if(by<ry) nby -= 1;
else nry -= 1;
}
else if(d==2){
if(by>ry) nby += 1;
else nry += 1;
}
}
}
if(isVisited[nby][nbx][nry][nrx]) continue;
isVisited[nby][nbx][nry][nrx] = 1;
q.push({nby, nbx, nry, nrx});
}
}
ans++;
}
cout << -1 << endl;
}
int main(void){
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> h >> w;
for(int i=0; i<h; i++){
for(int j=0; j<w; j++){
cin >> mat[i][j];
if(mat[i][j] == 'B'){
by=i; bx=j;
mat[i][j] = '.';
}
if(mat[i][j] == 'R'){
ry=i;rx=j;
mat[i][j] = '.';
}
}
}
solution();
}
|
cs |
시행착오
반응형
'코딩 공부 > 백준' 카테고리의 다른 글
| [백준][C++] 1368 물대기 (0) | 2021.04.11 |
|---|---|
| [백준][C++] 12100 2048 (Easy) (0) | 2021.04.10 |
| [백준][C++] 1445 일요일 아침의 데이트 (0) | 2021.04.10 |
| [백준][C++] 17780 새로운 게임 (0) | 2021.04.09 |
| [백준][C++] 14464 소가 길을 건너간 이유 4 (0) | 2021.04.05 |