https://www.acmicpc.net/problem/2234
2234번: 성곽
첫째 줄에 두 정수 n, m이 주어진다. 다음 m개의 줄에는 n개의 정수로 벽에 대한 정보가 주어진다. 벽에 대한 정보는 한 정수로 주어지는데, 서쪽에 벽이 있을 때는 1을, 북쪽에 벽이 있을 때는 2를,
www.acmicpc.net
저는 두 번의 bfs를 사용하였습니다.
한번은 각 방의 넘버링을 위한 bfs, 다른 한번은 각 방에 인접한 방을 찾기 위한 bfs입니다.
최종으로 구해야 할 것이
1. 이 성에 있는 방의 개수
2. 가장 넓은 방의 넓이
3. 하나의 벽을 제거하여 얻을 수 있는 가장 넓은 방의 크기
이렇게 됩니다.
저는 1, 2번은 각 방의 넘버링으로 해결하였고, 3번은 각 방에 인접한 방을 찾아서 해결하였습니다.
이 문제에서 입력으로 주어지는 숫자는 벽에 대한 정보입니다.
서쪽에 벽이 있으면 1, 북쪽에 벽이 있으면 2, 동쪽에 벽이 있으면 4, 남쪽에 벽이 있으면 8을 더한 값이 주어집니다.
만약에 벽이 없으면 하나도 더해지지 않은 0이 주어질 것이고, 사방에 모두 벽이 있으면 1 + 2 + 4 + 8 = 15가 주어질 것입니다.
1, 2, 4, 8을 더한 값이 주어지기 때문에 먼저 비트마스킹을 떠올렸습니다.
벽을 체크하기 위해 wall 배열에 해당 방향에 대한 값을 넣었고,
해당 방향을 체크할 때 해당하는 값인 wall[i]과 list[x][y]를 비교하여
list[x][y] & wall[i]이 0이면 벽이 없는 것이고, 0이 아니면 벽이 있는 것이라고 보시면 되겠습니다.
bfs & 비트마스킹으로 각 방에 넘버링을 하였고, 넘버링을 하면서 방의 크기도 같이 구하였습니다.
그 다음 bfs를 한번 더 돌려서 인접한 방 번호를 sideroom에 넣었고 방의 크기 + 인접한 방의 크기를 비교하여 최댓값을 출력하였습니다.
(sideroom을 set으로 한 이유는 중복체크를 하기 위함입니다.)
[C++]
|
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
|
#include <iostream>
#include <queue>
#include <algorithm>
#include <cstring>
#include <set>
using namespace std;
set<int> sideroom[2501];
int N, M, wall[4] = { 4, 8, 1, 2 };
int list[50][50], direct[4][2] = { {0,1}, {1,0}, {0,-1}, {-1,0} };
int roomnum, maxroomsize, Room[50][50], Roomsize[2501];
bool visit[50][50];
void sidechk(int sx, int sy, int num) {
queue<pair<int, int> > q;
q.push({ sx, sy });
visit[sx][sy] = true;
while (!q.empty()) {
int x = q.front().first;
int y = q.front().second;
q.pop();
for (int i = 0; i < 4; i++) {
int nx = x + direct[i][0];
int ny = y + direct[i][1];
if (nx < 0 || ny < 0 || nx >= N || ny >= M) continue;
if (Room[nx][ny] != num) {
sideroom[num].insert(Room[nx][ny]);
continue;
}
if (visit[nx][ny]) continue;
q.push({ nx, ny });
visit[nx][ny] = true;
}
}
}
void bfs(int sx, int sy, int num) {
queue<pair<int, int> > q;
q.push({ sx, sy });
visit[sx][sy] = true;
for (int t = 1; ; t++) {
int x = q.front().first;
int y = q.front().second;
q.pop();
Room[x][y] = num;
for (int i = 0; i < 4; i++) {
if (wall[i] & list[x][y]) continue;
int nx = x + direct[i][0];
int ny = y + direct[i][1];
if (visit[nx][ny]) continue;
q.push({ nx, ny });
visit[nx][ny] = true;
}
if (q.empty()) {
Roomsize[num] = t;
maxroomsize = max(maxroomsize, t);
break;
}
}
}
void solve() {
int maxroomsum = 0;
cout << roomnum << '\n' << maxroomsize << '\n';
for (int i = 1; i <= roomnum; i++) {
set<int>:: iterator iter;
for (iter = sideroom[i].begin(); iter != sideroom[i].end(); iter++) {
int s = *iter;
maxroomsum = max(maxroomsum, Roomsize[i] + Roomsize[s]);
}
}
cout << maxroomsum << '\n';
}
void func() {
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
if (visit[i][j]) continue;
bfs(i, j, ++roomnum);
}
}
memset(visit, false, sizeof(visit));
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
if (visit[i][j]) continue;
sidechk(i, j, Room[i][j]);
}
}
}
void input() {
cin >> M >> N;
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
cin >> list[i][j];
}
}
}
int main() {
cin.tie(NULL); cout.tie(NULL);
ios::sync_with_stdio(false);
input();
func();
solve();
return 0;
}
|
cs |
[Java]
|
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
|
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Deque;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Set;
import java.util.StringTokenizer;
public class Main {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static StringTokenizer st;
static int list[][] = new int[51][51];
static int div[][] = new int[51][51];
static boolean visit[][] = new boolean[51][51];
static ArrayList<Integer> roomarea = new ArrayList<>();
static Set<Integer> s[];
static int wall[] = { 4, 8, 1, 2 };
static int direct[][] = { { 0, 1 }, { 1, 0 }, { 0, -1 }, { -1, 0 } };
static int N, M, roomcnt, maxarea, cnt, ans;
static void sidechk(int sx, int sy) {
Deque<int[]> dq = new ArrayDeque<>();
dq.add(new int[] { sx, sy });
visit[sx][sy] = true;
while (!dq.isEmpty()) {
int x = dq.peek()[0];
int y = dq.poll()[1];
for (int i = 0; i < 4; i++) {
int nx = x + direct[i][0];
int ny = y + direct[i][1];
if (nx < 0 || ny < 0 || nx >= N || ny >= M)
continue;
if (visit[nx][ny])
continue;
if (div[x][y] != div[nx][ny])
s[div[x][y]].add(div[nx][ny]);
else {
dq.add(new int[] { nx, ny });
visit[nx][ny] = true;
}
}
}
}
static void solveroom(int sx, int sy) {
Deque<int[]> dq = new ArrayDeque<>();
dq.add(new int[] { sx, sy });
visit[sx][sy] = true;
while (!dq.isEmpty()) {
int x = dq.peek()[0];
int y = dq.poll()[1];
div[x][y] = roomcnt;
cnt++;
for (int i = 0; i < 4; i++) {
int nx = x + direct[i][0];
int ny = y + direct[i][1];
if (nx < 0 || ny < 0 || nx >= N || ny >= M)
continue;
if (visit[nx][ny] || (wall[i] & list[x][y]) > 0)
continue;
dq.add(new int[] { nx, ny });
visit[nx][ny] = true;
}
}
}
static void func() {
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
if (visit[i][j])
continue;
solveroom(i, j);
roomarea.add(cnt);
roomcnt++;
maxarea = Math.max(maxarea, cnt);
cnt = 0;
}
}
s = new HashSet[roomcnt];
for (int i = 0; i < roomcnt; i++)
s[i] = new HashSet<>();
for (int i = 0; i < N; i++)
Arrays.fill(visit[i], false);
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
if (visit[i][j])
continue;
sidechk(i, j);
}
}
}
static void solve() {
for (int i = 0; i < roomcnt; i++) {
Iterator<Integer> iter = s[i].iterator();
while (iter.hasNext()) {
ans = Math.max(ans, roomarea.get(i) + roomarea.get(iter.next()));
}
}
System.out.println(roomcnt + "\n" + maxarea + "\n" + ans);
}
static void input() throws Exception {
st = new StringTokenizer(br.readLine());
M = Integer.parseInt(st.nextToken());
N = Integer.parseInt(st.nextToken());
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < M; j++) {
list[i][j] = Integer.parseInt(st.nextToken());
}
}
}
public static void main(String[] args) throws Exception {
input();
func();
solve();
}
}
|
cs |
'algorithm > bfs' 카테고리의 다른 글
| boj 17142 연구소 3 (0) | 2021.01.22 |
|---|---|
| boj 2636 치즈 (0) | 2021.01.22 |
| boj 1039 교환 (0) | 2021.01.22 |
| boj 3055 탈출 (0) | 2021.01.22 |
| boj 17472 다리 만들기 2 (0) | 2021.01.22 |