백준알고리즘
거울 설치
먼지의삶
2019. 10. 9. 20:53
https://www.acmicpc.net/problem/2151
2151번: 거울 설치
첫째 줄에 집의 크기 N (1 ≤ N ≤ 50)이 주어진다. 다음 N개의 줄에는 N개의 문자로 집에 대한 정보가 주어진다. ‘#’는 문이 설치된 곳으로 항상 두 곳이며, ‘.’은 아무 것도 없는 것으로 빛은 이 곳을 통과한다. ‘!’은 거울을 설치할 수 있는 위치를 나타내고, ‘*’은 빛이 통과할 수 없는 벽을 나타낸다.
www.acmicpc.net
|
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
|
#include<iostream>
#include<queue>
using namespace std;
int n;
string map[50];
int sx, sy, ex, ey;
int dx[] = { 0,0,1,-1 }; int dy[] = { 1,-1,0,0 };
bool d[50][50]; int dist[50][50];
struct info {
int x, y, cnt, dir;
info(int x, int y, int cnt, int dir) {
this->x = x;
this->y = y;
this->cnt = cnt;
this->dir = dir;
}
};
void bfs() {
queue<info> q;
for (int i = 0; i < 4; i++) {
int nx = sx + dx[i]; int ny = sy + dy[i];
if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue;
if (map[nx][ny] == '*') continue;
q.push(info(sx, sy, 0, i));
}
d[sx][sy] = true;
while (!q.empty()) {
int x = q.front().x; int y = q.front().y; int cnt = q.front().cnt; int dir = q.front().dir;
q.pop(); //cout << x << ' ' << y << ' ' <<dir<< endl;
int nx = x; int ny = y;
for (int i = 0; i < n; i++) {
nx += dx[dir]; ny += dy[dir];
if (nx < 0 || nx >= n || ny < 0 || ny >= n) break;
if (map[nx][ny] == '*') break;
if (d[nx][ny] == false) {
d[nx][ny] = true;
dist[nx][ny] = cnt;
if (map[nx][ny] == '.') {
q.push(info(nx, ny, cnt, dir));
}
if (map[nx][ny] == '!') {
for (int j = 0; j < 4; j++) {
if (dir == j) continue;
if (dir == 0 && j == 1) continue;
if (dir == 1 && j == 0) continue;
if (dir == 2 && j == 3) continue;
if (dir == 3 && j == 2)continue;
q.push(info(nx, ny, cnt + 1, j));
}
}
}
else if(d[nx][ny]){
if (dist[nx][ny] > cnt) {
dist[nx][ny] = cnt;
if (map[nx][ny] == '.') {
q.push(info(nx, ny, cnt, dir));
}
if (map[nx][ny] == '!') {
for (int j = 0; j < 4; j++) {
if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue;
if (dir == j) continue;
if (dir == 0 && j == 1) continue;
if (dir == 1 && j == 0) continue;
if (dir == 2 && j == 3) continue;
if (dir == 3 && j == 2)continue;
q.push(info(nx, ny, cnt + 1, j));
}
}
}
}
}
}
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> n;
for (int i = 0; i < n; i++) {
cin >> map[i];
}
int trash = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (map[i][j] == '#') {
if (trash == 0) {
sx = i; sy = j;
}
else {
ex = i; ey = j;
}
trash++;
if (trash == 2) break;
}
}
}
bfs();
/*for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cout << dist[i][j] << ' ';
}cout << '\n';
}*/
cout << dist[ex][ey] << '\n';
return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#4f4f4ftext-decoration:none">Colored by Color Scripter
|
BFS문제다.
로봇, 레이저통신 문제랑 비슷한 풀이인데, 방향성 + BFS의 문제가 아닌가싶다.
딱히 주의할점은 없는듯 굉장히 직관적인문제