반응형
2931번: 가스관
러시아 가스를 크로아티아로 운반하기 위해 자그레브와 모스코바는 파이프라인을 디자인하고 있다. 두 사람은 실제 디자인을 하기 전에 파이프 매니아 게임을 이용해서 설계를 해보려고 한다.
www.acmicpc.net
알고리즘 종류
- 구현
사고 과정
- 가스는 한 방향으로 이동한다. 따라서 이동하는 좌표와 방향을 기록하면서 중간에 끊긴 좌표를 찾으면 된다.
1. M과 Z의 위치를 기록한다.
2. 시작점 M의 4방향을 탐색하여 연결된 파이프가 있는 쪽에 방향을 설정한다.
2-1. 만약에 4방향에 연결된 파이프가 없으며, Z를 시작점으로 변경한다.
3. DFS 또는 BFS를 이용하여, 가스를 이동시켜본다.
3-1. 본인은 BFS를 사용하여 큐에 y, x, d를 저장했다.
4. 문제의 좌표를 찾았다면, 4방향을 탐색하여 주변 파이프와 연결이 가능한 파이프를 찾는다.
구현(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
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
|
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int r, c;
int py, px;
vector<pair<int, int> > v(2);
char mat[30][30];
int dir[4][2] = {{1,0}, {0,1}, {-1,0}, {0,-1}};
bool isValid(int y, int x){
return (y>=1 && y<=r) && (x>=1 && x<=c);
}
void find_pipe(){
// .인 곳의 4방향을 탐색한다.
int arr[4] = {0};
for(int d=0; d<4; d++){
int ny = py + dir[d][0];
int nx = px + dir[d][1];
if(d==0){
if(mat[ny][nx] == '|' || mat[ny][nx] == '+' || mat[ny][nx] == '2' || mat[ny][nx] == '3') arr[d] = 1;
}
else if(d==1){
if(mat[ny][nx] == '-' || mat[ny][nx] == '+' || mat[ny][nx] == '3' || mat[ny][nx] == '4') arr[d] = 1;
}
else if(d==2){
if(mat[ny][nx] == '|' || mat[ny][nx] == '+' || mat[ny][nx] == '1' || mat[ny][nx] == '4') arr[d] = 1;
}
else if(d==3){
if(mat[ny][nx] == '-' || mat[ny][nx] == '+' || mat[ny][nx] == '1' || mat[ny][nx] == '2') arr[d] = 1;
}
}
// 아래 경우에 따라 답을 출력한다.
if(arr[0] && arr[1] && arr[2] && arr[3]){
cout << py << " " << px << " " << "+";
}else if(arr[0] && !arr[1] && arr[2] && !arr[3]){
cout << py << " " << px << " " << "|";
}else if(!arr[0] && arr[1] && !arr[2] && arr[3]){
cout << py << " " << px << " " << "-";
}else if(arr[0] && arr[1] && !arr[2] && !arr[3]){
cout << py << " " << px << " " << "1";
}else if(!arr[0] && arr[1] && arr[2] && !arr[3]){
cout << py << " " << px << " " << "2";
}else if(!arr[0] && !arr[1] && arr[2] && arr[3]){
cout << py << " " << px << " " << "3";
}else if(arr[0] && !arr[1] && !arr[2] && arr[3]){
cout << py << " " << px << " " << "4";
}
}
int check_dir(int y, int x){
int d=-1;
for(int i=0; i<4; i++){
int ny = y + dir[i][0];
int nx = x + dir[i][1];
if(!isValid(ny, nx)) continue;
if(mat[ny][nx] == '.') continue;
if(i==0){
if(mat[ny][nx] == '|' || mat[ny][nx] == '+' || mat[ny][nx] == '2' || mat[ny][nx] == '3') d=0;
}
else if(i==1){
if(mat[ny][nx] == '-' || mat[ny][nx] == '+' || mat[ny][nx] == '3' || mat[ny][nx] == '4') d=1;
}
else if(i==2){
if(mat[ny][nx] == '|' || mat[ny][nx] == '+' || mat[ny][nx] == '1' || mat[ny][nx] == '4') d=2;
}
else if(i==3){
if(mat[ny][nx] == '-' || mat[ny][nx] == '+' || mat[ny][nx] == '1' || mat[ny][nx] == '2') d=3;
}
}
return d;
}
void search(){
// 시작점과 시작 방향을 탐색
int y = v[0].first;
int x = v[0].second;
int d = check_dir(y, x);
// 시작 방향이 -1이라는 뜻은 M 주변에 파이프가 없다는 뜻이다. 따라서, Z부터 시작하자
if(d==-1){
y = v[1].first;
x = v[1].second;
d = check_dir(y, x);
}
// 시작 좌표와 방향을 넣는다.
queue<pair<pair<int, int>, int> > q;
q.push({{y, x}, d});
while(!q.empty()){
y = q.front().first.first;
x = q.front().first.second;
d = q.front().second;
q.pop();
int ny = y + dir[d][0];
int nx = x + dir[d][1];
int nd;
// .를 마주하면 종료한다.
if(mat[ny][nx] == '.'){
py = ny;
px = nx;
return;
}
// 다음 지점의 파이프 모양에 따라 다음 방향을 결정한다.
if(d==0){
if(mat[ny][nx] == '|' || mat[ny][nx] == '+') nd = 0;
else if(mat[ny][nx] == '2') nd = 1;
else if(mat[ny][nx] == '3') nd = 3;
}
else if(d==1){
if(mat[ny][nx] == '-' || mat[ny][nx] == '+') nd = 1;
else if(mat[ny][nx] == '3') nd = 2;
else if(mat[ny][nx] == '4') nd = 0;
}
else if(d==2){
if(mat[ny][nx] == '|' || mat[ny][nx] == '+') nd = 2;
else if(mat[ny][nx] == '1') nd = 1;
else if(mat[ny][nx] == '4') nd = 3;
}
else if(d==3){
if(mat[ny][nx] == '-' || mat[ny][nx] == '+') nd = 3;
else if(mat[ny][nx] == '1') nd = 0;
else if(mat[ny][nx] == '2') nd = 2;
}
// 다음 지점과 방향을 저장한다.
q.push({{ny, nx}, nd});
}
}
int main(void){
ios_base::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin >> r >> c;
// 입력 받고, 시작점이 될 M 그리고 예비 시작점 Z를 저장
char s;
for(int i=1; i<=r; i++){
for(int j=1; j<=c; j++){
cin >> s;
mat[i][j] = s;
if(s == 'M'){
v[0] = {i, j};
}
else if(s == 'Z'){
v[1] = {i, j};
}
}
}
search();
find_pipe();
}
|
cs |
시행착오
- 본인이 처음 작성한 코드는 단순하지만 추상화가 되어 있지 않았다. BFS를 통해서 시작점에서 뻗어나가도록 설계했다. 뻗어나갈 때, 4방향을 탐색하도록 했다. 그런데 문제를 다시 읽어보니 굳이 4방향을 모두 탐색할 필요가 없었다. 왜냐하면, 가스는 한 방향으로 이동하기 때문이다. 그럼 4방향을 탐색하지 않고 가스가 다음 위치를 알기 위해서는 방향이 필요했다. 결국, 방향 변수를 만들었다.
- 굳이 BFS를 사용한 이유는 본인은 그래프에서 이동할 때 BFS를 쓰는 것을 선호하기 때문이다.
- 정리하자면, 이 문제는 파이프를 만났을 때에 방향을 설정하는 문제이다.
반응형
'코딩 공부 > 백준' 카테고리의 다른 글
| [백준][C++] 13905 세부 (0) | 2021.03.13 |
|---|---|
| [백준][C++] 14621 나만 안되는 연애 (0) | 2021.03.13 |
| [백준][C++] 10993 별 찍기 - 18 (0) | 2021.03.12 |
| [백준][C++] 2665 미로만들기 (0) | 2021.03.04 |
| [백준][C++] 5639 이진 검색 트리 (0) | 2021.03.03 |