[백준 2234] 성곽 (C++)
2234번: 성곽
첫째 줄에 두 정수 n, m이 주어진다. 다음 m개의 줄에는 n개의 정수로 벽에 대한 정보가 주어진다. 벽에 대한 정보는 한 정수로 주어지는데, 서쪽에 벽이 있을 때는 1을, 북쪽에 벽이 있을 때는 2를,
www.acmicpc.net
비트마스킹, BFS
[백준 16946] 벽 부수고 이동하기 4 (C++)
16946번: 벽 부수고 이동하기 4 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 한 칸에서 다른 칸으로 이동하려면, 두
hyeo-noo.tistory.com
위 문제와 아주 비슷한 방법을 적용해서 풀었다.
차이점은 N과 M의 크기가 현재 문제에서는 50, 50이 최대라서 O(N^2 * M^2)이 가능하다는 점이다.
이때문에 풀이가 비슷함에도 불구하고 난이도 차이가 2단계나 난 것 같다.
Map의 각 칸마다 0~15까지의 주어진 수를 저장해놓고 연속된 칸을 찾기위해서 bfs를 수행했다.
문제에서 대놓고 비트마스킹을 사용하라고 해서 편하게 적용할 수 있었다.
dir[]배열의 순서가 서, 북, 동, 남 이므로 dr[], dc[]배열도 서, 북, 동, 남 순으로 배치해 주었다.
다음 칸을 아직 방문하지 않았고 해당 방향으로 벽이 뚫려 있다면 탐색할 수 있게 하고, 현재 bfs의 setcount를 각 칸에 맞는 setMap[][]의 값으로 설정해 주었다.
위 과정에서 1, 2번 답을 구할 수 있다.
그리고 3번 답을 구하기 위해서 모든 칸들을 순회한다.
현재 칸에서 4방향으로 둘러보고 인접 칸이 현재 칸과 같은 집합이 아니라면 인접 칸의 크기를 더해준다.
|
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
|
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cstring>
#define fasti ios_base::sync_with_stdio(false); cin.tie(0);
#define fastio ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define INF 1e9+7
#define pii pair<int, int>
typedef long long ll;
// typedef pair<int, int> pii;
using namespace std;
int N, M;
int Map[51][51];
int setMap[51][51];
int setnum[2505];
int setcount = 1;
int dr[4] = {0, -1, 0, 1}, dc[4] = {-1, 0, 1, 0};
int dir[4] = {1, 1 << 1, 1 << 2, 1 << 3}; // 서 북 동 남
void input(){
cin >> M >> N;
for(int r = 0; r < N; r++){
for(int c = 0; c < M; c++){
cin >> Map[r][c];
}
}
}
int bfs12(int r, int c){
int cnt = 0;
queue<pii > que;
que.push({r, c});
setMap[r][c] = setcount;
while(!que.empty()){
pii now = que.front();
que.pop();
cnt++;
for(int k = 0; k < 4; k++){
int nr = now.first + dr[k];
int nc = now.second + dc[k];
// 뚫려 있는 경우
if(!(dir[k] & Map[now.first][now.second]) && !setMap[nr][nc]){
setMap[nr][nc] = setcount;
que.push({nr, nc});
}
}
}
setnum[setcount] = cnt;
setcount++;
return cnt;
}
int find3(int r, int c){
int ret = setnum[setMap[r][c]];
for(int k = 0; k < 4; k++){
int nr = r + dr[k];
int nc = c + dc[k];
if(nr < 0 || nr >= N || nc < 0 || nc >= M) continue;
if(setMap[nr][nc] != setMap[r][c]){
ret = max(ret, setnum[setMap[r][c]] + setnum[setMap[nr][nc]]);
}
}
return ret;
}
void solve(){
int number_of_rooms_in_this_castle = 0, largest_room_area = 0;
int largest_room_size_obtained_by_removing_one_wall = 0;
for(int r = 0; r < N; r++){
for(int c = 0; c < M; c++){
if(setMap[r][c]) continue;
largest_room_area = max(largest_room_area, bfs12(r, c));
number_of_rooms_in_this_castle++;
}
}
for(int r = 0; r < N; r++){
for(int c = 0; c < M; c++){
largest_room_size_obtained_by_removing_one_wall = \
max(largest_room_size_obtained_by_removing_one_wall, find3(r, c));
}
}
cout << number_of_rooms_in_this_castle << "\n";
cout << largest_room_area << "\n";
cout << largest_room_size_obtained_by_removing_one_wall << "\n";
}
int main(){
fastio
input();
solve();
return 0;
}
|
cs |