문제 조건을 잘못 이해하여 헤맸던 문제였다.
1. 벽이 부서진 곳을 기점으로 하여 새로 생성된 cluster를 찾아야 한다.
2. 또한, cluster 중 하나라도 바닥에 닿아 있다면, 그 cluster는 중력의 영향을 받지 않는다.
코드
|
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
|
#include<iostream>
#include<vector>
using namespace std;
int R, C, N;
char map[101][101];
bool visit[101][101];
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};
vector<pair<int, int> > cluster;
bool floor_check;
void init()
{
for(int i=1; i<=R; i++)
for(int j=1; j<=C; j++)
visit[i][j] = false;
}
void dfs(int x, int y)
{
visit[x][y] = true;
if (x == R)
{
floor_check = true;
return ;
}
for(int i=0; i<4; i++)
{
int nx = x + dx[i];
int ny = y + dy[i];
if (nx <= 0 || ny <= 0 || nx > R || ny > C)
continue;
if (map[nx][ny] == 'x' && !visit[nx][ny])
{
visit[nx][ny] = true;
cluster.push_back(make_pair(nx, ny));
dfs(nx, ny);
}
}
}
int main()
{
cin.tie(NULL);
ios_base::sync_with_stdio(false);
cin >> R >> C;
int clus = 0;
for(int i=1; i<=R; i++)
for(int j=1; j<=C; j++)
cin >> map[i][j];
cin >> N;
for(int i=0; i<N; i++)
{
int h;
int b_point = -1;
cin >> h;
h = R - h + 1;
if (i % 2 == 0)
{
for(int j=1; j<=C; j++)
{
if (map[h][j] == 'x')
{
b_point = j;
break;
}
}
}
else
{
for(int j=C; j>=1; j--)
{
if (map[h][j] == 'x')
{
b_point = j;
break;
}
}
}
if (b_point == -1)
continue;
map[h][b_point] = '.'; //벽이 부숴진 곳을 기준으로 하여 dfs탐색
for(int j=0; j<4; j++)
{
int nx = h + dx[j];
int ny = b_point + dy[j];
if (nx <= 0 || ny <= 0 || nx > R || ny > C)
continue;
if (map[nx][ny] == '.')
continue;
init();
cluster.clear();
floor_check = false;
cluster.push_back(make_pair(nx, ny));
dfs(nx, ny);
if (floor_check) //클러스터 중 하나라도 바닥에 닿아 있다면?
continue;
while (1)
{
bool down = true;
for(int k = 0; k < cluster.size(); k++)
map[cluster[k].first][cluster[k].second] = '.';
for(int k = 0; k < cluster.size(); k++)
{
int x = cluster[k].first + 1;
int y = cluster[k].second;
if (x == R + 1 || map[x][y] == 'x') //하나라도 닿았다면?
{
down = false;
break;
}
}
for(int k=0; k < cluster.size(); k++)
{
if (down)
cluster[k].first++;
map[cluster[k].first][cluster[k].second] = 'x';
}
if (!down)
break;
}
}
}
for(int i=1; i<=R; i++)
{
for(int j=1; j<=C; j++)
{
printf("%c", map[i][j]);
}
printf("\n");
}
return (0);
}
|
cs |
그리고 cluster 별 이동을 어떻게 할지 고민했었는데, 부서진 곳을 기점으로 상하좌우로 탐색하였을 때 만나는 Cluster의 좌표들을 vector에다가 저장해놓고, 그 좌표들을 이용하여 이동시키면 되었다.
원래의 생각 -> visit 배열로 cluster number를 지정하여 visit[i][j]가 같은 것끼리 움직이게 하려고 하였는데, 이렇게 구현하기 위해서는 visit 배열 전체를 계속 탐색해야해서 비효율적이다. 따라서, 해당 클러스터의 좌표들을 벡터로 따로 저장하여 푸는 것이 좋다.
'Study > BOJ' 카테고리의 다른 글
| BOJ - 네트워크 연결(1922) (0) | 2021.04.15 |
|---|---|
| BOJ - 거짓말(1043) (0) | 2021.04.14 |
| BOJ - 최소 스패닝 트리(1197) (0) | 2021.04.14 |
| BOJ - 청소년 상어(19236) (0) | 2021.04.10 |
| BOJ - 마법사 상어와 파이어스톰(20058) (0) | 2021.04.10 |
