[BOJ] 2151. 거울설치 + TC

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

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

 

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

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

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

 

3

...

*!#

#!!

 

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

 

 

#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; } 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