https://www.acmicpc.net/problem/5547
5547번: 일루미네이션
첫째 줄에 두 개의 정수 W와 H가 주어진다. (1 ≤ W, H ≤ 100) 다음 H줄에는 상근이네 집의 건물 배치가 주어진다. i+1줄에는 W개의 정수가 공백으로 구분되어 있다. j번째 (1 ≤ j ≤ w) 정수의 좌표는
www.acmicpc.net
위 그림의 좌표와 상관없이 저는 (1, 1) ~ (N, M)으로 입력을 받았습니다.
나중에 x의 좌표에 따라 인접하는 좌표들만 구분하면 되는 것입니다.
이 문제의 핵심은 건물 외부 체크를 어떻게 하느냐입니다.
왼쪽 건물들을 보시면 내부에도 흰색이 존재합니다. 이거를 잘 걸러내야 합니다.
저는 배열의 크기를 (N + 2, M + 2)로 설계하였고,
(1, 1) ~ (N, M)에 건물 정도를 입력 받아 가장자리에 있는 좌표에는 모두 건물 외부가 올 수 있게끔 하였습니다.
(0, 0)이나 (N + 1, M + 1)에 있는 것은 무조건 건물 외부 (흰색) 입니다.
그러면 무조건 흰색이 되는 (0, 0)을 시작으로 bfs를 돌려 건물 외부들을 모두 체크할 수있습니다.
이후 건물을 bfs로 순회하여 각 좌표에서 인접한 건물이 몇 개 있는지 세어 줍니다.
이 때, 건물 외부의 흰색은 카운팅을 하지 않으며, 건물 내부의 흰색은 카운팅을 합니다.
그래야 건물 내부에도 조명을 설치하지 않습니다. [위 사진 기준 (2, 3)이 예시입니다.]
카운팅이 완료되었으면 해당 좌표에서 조명을 설치할 벽면의 길이를 구합니다.
벽면의 길이는 인접한 건물이 0개 ~ 6개인 경우가 동일하므로 직접 그려보시면 알 수 있습니다.
|
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
|
#include <iostream>
#include <algorithm>
#include <queue>
#define MAX 103
#define LEN 6
using namespace std;
typedef pair<int, int> pi;
int list[MAX][MAX];
bool visit[MAX][MAX], sideChk[MAX][MAX];
int direct[2][6][2] = {
{{-1,-1},{-1,0},{0,1},{1,0},{1,-1},{0,-1}},
{{0,-1},{-1,0},{-1,1},{0,1},{1,1},{1,0}}
};
int len[7];
int N, M, ans;
void sideBfs(int sx, int sy) {
queue<pi> q;
q.push({ sx,sy });
sideChk[sx][sy] = true;
while (!q.empty()) {
int x = q.front().first;
int y = q.front().second;
q.pop();
int idx = x % 2;
for (int d = 0; d < 6; d++) {
int nx = x + direct[idx][d][0];
int ny = y + direct[idx][d][1];
if (nx < 0 || ny < 0 || nx > N + 1 || ny > M + 1) continue;
if (list[nx][ny] || sideChk[nx][ny]) continue;
q.push({ nx,ny });
sideChk[nx][ny] = true;
}
}
}
void bfs(int sx, int sy) {
queue<pi> q;
q.push({ sx,sy });
visit[sx][sy] = true;
while (!q.empty()) {
int x = q.front().first;
int y = q.front().second;
q.pop();
int cnt = 0;
int idx = x % 2;
for (int d = 0; d < 6; d++) {
int nx = x + direct[idx][d][0];
int ny = y + direct[idx][d][1];
if (nx <= 0 || ny <= 0 || nx > N + 1 || ny > M + 1) continue;
if (!list[nx][ny]) {
if (!sideChk[nx][ny]) cnt++;
continue;
}
cnt++;
if (visit[nx][ny]) continue;
q.push({ nx,ny });
visit[nx][ny] = true;
}
ans += len[cnt];
}
}
void func() {
sideBfs(0, 0);
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= M; j++) {
if (!list[i][j] || visit[i][j]) continue;
bfs(i, j);
}
}
cout << ans << '\n';
}
void init() {
for (int i = 0; i <= LEN; i++) {
len[i] = LEN - i;
}
}
void input() {
cin >> M >> N;
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= M; j++) {
cin >> list[i][j];
}
}
}
int main() {
cin.tie(NULL); cout.tie(NULL);
ios::sync_with_stdio(false);
init();
input();
func();
return 0;
}
|
cs |
'algorithm > bfs' 카테고리의 다른 글
| boj 18112 이진수 게임 (2) | 2022.09.16 |
|---|---|
| boj 16946 벽 부수고 이동하기 4 (0) | 2022.05.22 |
| boj 16932 모양 만들기 (0) | 2022.05.14 |
| boj 17244 아맞다우산 (0) | 2021.11.25 |
| boj 1194 달이 차오른다, 가자. (0) | 2021.04.21 |