본문 바로가기

BOJ/C++

[BOJ] 2151. 거울설치 + TC

*거울이 [\] [/] 이 두 방향으로 있다고 생각하고 풀어야 한다. 

처음에는 45도이기 때문에 [/] 만 생각하고 풀었다가 아니라는 것을 알게 됐다. 

 

*처음 [#] 좌표에서 출발해서 4방향 모두 큐에 넣는다. 

*각 방향으로 한 칸 앞으로 전진한 좌표가 거울이면 방향을 바꾸어서 큐에 넣고, 방향을 바꾸지 않는 상태로도 큐에 넣는다. 

이 좌표에 거울을 설치하지 않는 경우도 생각한다. 

 

3

...

*!#

#!!

 

이 예시를 보면 (1, 3)에서 출발해서 (3,1)로 가야하는데 남쪽 방향으로 (3,3)의 거울로 간 후, 방향을 한 번 바꾸면 바로 (3,1)에 접근가능하다. 

 

 

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
#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
#include <functional>
#define INF 987654321
using namespace std;
 
int n, ans = INF;
char map[51][51];
typedef pair<int, int> pp;
typedef pair<pp, pp> pppp;
 
vector<pp> door;
int dp[51][51];
bool visited[51][51][4];
int dx[4] = { -1,1,0,0 }, dy[4] = { 0,0,-1,1 };
 
void bfs() {
    priority_queue<pppp, vector<pppp>, greater<pppp>> q;
 
    for (int i = 0; i < 4; i++) {
 
        q.push(pppp(pp(0, i), door[0]));
        visited[door[0].first][door[0].second][i] = true;
    }
 
    while (!q.empty()) {
        int x = q.top().second.first;
        int y = q.top().second.second;
        int cnt = q.top().first.first;
        int dir = q.top().first.second;
        q.pop();
 
        //들어온 방향에 따라 반사되는 방향이 달라진다.
        if (x == door[1].first && y == door[1].second) {
            ans = ans > cnt ? cnt : ans;
            continue;
        }
        //거울은 45도 방향으로 놓여져 있다.
        int nx = x + dx[dir];
        int ny = y + dy[dir];
 
        if (nx < 0 || nx >= n || ny < 0 || ny >= n || map[nx][ny] == '*' || visited[nx][ny][dir]) continue;
 
 
        if (map[nx][ny] == '!') {
            if (dir <= 1) {
 
                 
                q.push({ {cnt + 1, 2},{nx, ny} });
 
                 
                q.push({ {cnt + 1, 3},{nx, ny} });
            }
            else {
                 
                q.push({ {cnt + 1, 0},{nx, ny} });
 
                 
                q.push({ {cnt + 1, 1},{nx, ny} });
            }
 
        }
        //거울 설치 안하고 그냥 가는 방법도 있음
        visited[nx][ny][dir] = true;
        q.push({ {cnt, dir}, {nx, ny} });
 
    }
}
int main() {
 
    ios_base::sync_with_stdio(0);
    cin.tie(0);
 
    //양 쪽 문에서 서로가 보여야 하기 때문에 bfs를 두 번 돈다.
    cin >> n;
 
 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> map[i][j];
 
            if (map[i][j] == '#') {
                door.push_back({ i, j });
            }
 
        }
    }
    //문을 발견했을 때 나갈수 있는 방향은 모두 나가야 하나?
    //아니면 두 문의 상대적인 위치를 알아내서 -> 서로 마주볼 수 있는 방향으로???
 
    bfs();
 
 
    cout << ans << '\n';
 
 
    return 0;
}
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
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
4
..#.
!..#
.*..
!.!.
Answer: 3
 
4
#..!
....
....
#...
Answer: 0
 
4
#..!
!...
.#..
!!.!
Answer: 2
 
5
#!..!
**...
!!..!
.*..*
!!..#
Answer: 4
 
4
!!.!
#!*#
!.!!
!*!.
Answer: 2
 
5
..#..
!.!.!
*.*!!
...!*
#..!!
Answer: 5
 
4
#..!
!!.!
*!.*
#!..
Answer: 3
 
5
***#*
*.!!*
*.!!*
*!!.*
*#***
Answer: 4
 
5
***#*
*!!!*
*.*!*
*!!**
*#***
Answer: 2
 
3
#.!
!!*
.!#
Answer: 3
 
7
!!..!.#
*.....*
.!..!..
!!*.!.!
.*!!.*!
...!!..
!*#****
Answer: 5
 
4
#!!!
!!!!
!!!!
!!!#
Answer: 1
 
4
#!!*
*!!!
!*!!
*!*#
Answer: 3
 
2
#.
!#
Answer: 1
 
10
****#*****
!!..!.!..!
......*...
......!..!
*!....!..*
......!..!
.!....!...
...!*.*...
!..!!.!..!
****#*****
Answer: 8
 
50
#!..............................................*!
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
.!...............................................!
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
.*...........................................!...!
.!.......................!...................!...*
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
*................................................*
!!...............................................#
Answer: 8
 
9
.!*......
..!.!*!.!
#.!*.*.*.
!!.*!.!*.
.*.......
.#......!
.........
.........
!.......!
 
Correct answer:
3
 
input #1
3
#!.
!!.
*#.
 
output #1
1
 
input #2
3
...
*!#
#!!
 
output #2
1
 
input #3
2
!#
!#
 
output #3
0
 
input #4
30
#!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!#
 
output #4
1
   
20
#.....!.!...........
******.*.***********
*!....!*.***********
*.****.*.***********
*.**!.!*.***********
*.**.***.***********
*.**!.!*.***********
*.****.*.***********
*.**!.!*.***********
*.**.***.***********
*!..!.......#*******
********.***.*******
********.***.*******
********.***.*******
********.***.*******
********.*!.!*******
********.*.*********
********.*!.!*******
********.***.*******
********!...!*******
   
  ans = 4

'BOJ > C++' 카테고리의 다른 글

[BOJ] 10799. 쇠막대기 (C)  (0) 2020.03.24
[BOJ] 1158. 요세푸스 문제 (C)  (0) 2020.03.24
[BOJ] 9376. 탈옥  (0) 2020.03.18
[BOJ] 12094. 2048(Hard)  (0) 2020.03.18
[BOJ] 16638. 괄호 추가하기2  (0) 2020.03.17