728x90
문제
극악무도한 테러리스트 주현이가 도시를 습격했다. 습격받은 도시는 세로 N칸, 가로 N칸으로 이뤄진 격자 모양이며, 각 칸은 빈칸이거나 건물이 존재한다. 주현이는 자신이 만든 수제 폭탄을 건물이 없는 곳에 설치한다. 폭탄은 터질 때 상하좌우 각 방향에 대해 충격파가 퍼져나가는데, 충격파가 닿은 건물은 파괴되어 건물 잔해가 된다. 충격파는 건물 또는 건물 잔해에 닿고 난 뒤 소멸한다.
이번 테러 사건 수사를 맡은 향빈이는 현장을 재구성하는 중이다. 건물 잔해의 위치를 통해 어떤 위치에서 폭탄이 터졌는지 알아내고자 한다. 아무리 생각해도 폭탄의 위치를 알아낼 수 없는 향빈이는 문제 해결의 대가인 당신을 찾아왔다. 습격받은 도시의 정보가 주어졌을 때, 주현이가 설치한 폭탄의 위치를 구해주자.
입력
다음과 같이 입력이 주어진다.
N
a1,1a1,2⋯a1,Na2,1a2,2⋯a2,N⋮⋮⋱⋮aN,1aN,2⋯aN,N
출력
N개의 줄에 도시의 정보를 출력한다. 각 줄은 N개의 문자를 포함하며 i번째 줄 j번째 문자는 도시의 세로 i번째 가로 j번째 칸에 대한 정보이다. 빈칸일 경우 ., 건물일 경우 O, 건물 잔해일 경우 X, 폭탄이 설치된 칸인 경우 B이다. 답이 여러 가지인 경우, 아무거나 출력한다.
제한
- N은 도시의 크기이다. (1≤N≤2000)
- ai,j= . 또는 ai,j= O 또는 ai,j= X
- ai,j= . 면, 도시의 세로 i번째 가로 j번째 칸은 빈칸이다.
- ai,j= O 면, 도시의 세로 i번째 가로 j번째 칸은 건물이다.
- ai,j= X 면, 도시의 세로 i번째 가로 j번째 칸은 건물 잔해이다.
- 항상 답이 존재하는 경우만 주어진다.
나의 풀이
X를 지나는 수평 직선과 수직 직선을 만들어 각각의 직선들의 교점을 구한다. 교점이 .일 경우 B로 바꾼다.
|
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
|
#include <iostream>
#include <set>
#define MAX 2000
using namespace std;
string city[MAX][MAX];
set<int> ver;
set<int> hor;
typedef struct Point {
int x;
int y;
}Point;
Point IntersectionPoint(int a1, int b1, int c1, int a2, int b2, int c2) {
Point ret;
ret.x = -1 * (b1 * c2 - b2 * c1) / (a1 * b2 - a2 * b1);
ret.y = (-a1 / b1 * (b1 * c2 - b2 * c1) / (a1 * b2 - a2 * b1) - c1 / b1);
return ret;
}
int main() {
int n;
cin >> n; // 도시 크기
string c;
for (int i = 0;i < n;i++) {
cin >> c;
for (int j = 0;j<c.length();j++) {
city[i][j] = c[j];
if (c[j] == 'X') {
hor.insert(-i);
ver.insert(j);
}
}
} // 도시 정보 받기
Point result;
for (auto itr1 : hor) {
for (auto itr2 : ver) {
result = IntersectionPoint(0, 1, itr1, 1, 0, itr2);
if (city[result.y][result.x] == ".")
city[result.y][result.x] = "B";
else
continue;
}
}
for (int i = 0;i < n;i++) {
for (int j = 0;j < n;j++)
cout << city[i][j];
cout << endl;
}
return 0;
}
|
" target="_blank" rel="noopener" data-mce-href="http://
'C++ > BOJ' 카테고리의 다른 글
| #8 - 20946번 합성인수분해 (시간초과) (0) | 2021.08.16 |
|---|---|
| #7 - 20943번 카카오톡(오답) (0) | 2021.08.15 |
| #6 - 20937번 떡국 (0) | 2021.08.09 |
| #5 - 20944번 팰린드롬 척화비 (0) | 2021.08.09 |
| #4 - 16953번 A → B (0) | 2021.08.09 |