๋ฏธ๋ค๋(2933)
ํญ์ ์๋ฎฌ๋ ์ด์ ๋ฌธ์ ๊ฐ ์ด๋ ค์ ๋๊ฒ ๊ฐ๋ค. ์ด ๋ฌธ์ ๋ ๊ทธ๋ฌ๋ค.
์ด๋ป๊ฒ ํ์๋
r
๊ณผc
๋ ๋๊ตด์ ํฌ๊ธฐ์ด๋ค.mineral
์ ๋ฏธ๋ค๋์ ์์น๋ฅผ ์ ์ฅํ ๋ฐฐ์ด์ด๋ค.cluster
๋ ์ด๋ค ๋ฏธ๋ค๋ ํด๋ฌ์คํฐ์ ํฌํจ๋ ๋ฏธ๋ค๋์ ์์น๋ฅผ ์ ์ฅํ๊ณ ์๋ค.(first
๋ ํ,second
๋ ์ด)
๋ง๋๋ ์ผ์ชฝ๊ณผ ์ค๋ฅธ์ชฝ ๋ฒ๊ฐ์๊ฐ๋ฉฐ ๋์ ธ์ง๋ค. ์ด๋ ๋ง๋๋ฅผ ๋์ ธ ๋ฏธ๋ค๋์ด ํ๊ดด๋ ๋๋ง๋ค, ํ๊ดด๋ ๋ฏธ๋ค๋๊ณผ ์ฐ๊ฒฐ๋์ด์๋ ๋ฏธ๋ค๋๋ค์ด ์ค๋ ฅ์ ์ํด ์๋๋ก ๋จ์ด์ง๋์ง๋ฅผ ํ์ธํด์ผํ๋ค.
for(int i=0; i < N; i++){
int height;
scanf("%d", &height); // ๋์ ธ์ง ๋ง๋์ ๋์ด
height = r - height;
if(i%2 == 0){
// ์ผ์ชฝ์์ ์ค๋ฅธ์ชฝ์ผ๋ก ๋์ง ๊ฒฝ์ฐ
for(int j = 0; j < c; j++){
if(mineral[height][j] == 'x'){
mineral[height][j] = '.';
break;
}
}
} else {
// ์ค๋ฅธ์ชฝ์์ ์ผ์ชฝ์ผ๋ก ๋์ง ๊ฒฝ์ฐ
for(int j = c - 1; j >= 0; j--){
if(mineral[height][j] == 'x'){
mineral[height][j] = '.';
break;
}
}
}
dfsAll(); // ์ ์ฒด ๋ฏธ๋ค๋ ํด๋ฌ์คํฐ๋ฅผ ํ์ํ๋ค.
}
๋ง์ฝ ๋ฏธ๋ค๋์ด ํ๊ดด๋์ด ๋จ์ ๋ฏธ๋ค๋ ํด๋ฌ์คํฐ๊ฐ ๋ถ๋ฆฌ ๋๊ณ , ๋ถ๋ฆฌ๋ ํด๋ฌ์คํฐ๊ฐ ์ง๋ฉด๊ณผ ๋จ์ด์ ธ์๋ค๋ฉด, ์ด ํด๋ฌ์คํฐ๋ ์ค๋ ฅ์ ์ํด ๋จ์ด์ง๋ค. ๊ทธ๋์ ๋ถ๋ฆฌ๋ ํด๋ฌ์คํฐ์ ์ง๋ฉด๊ณผ์ ๊ฑฐ๋ฆฌ๋ฅผ ๊ณ์ฐํ์ฌ ํด๋ฌ์คํฐ์ ์์น๋ฅผ ๊ฐฑ์ ํ๋ค.
void dfsAll(){
memset(visited, false, sizeof(visited));
for(int i = 0; i < r; i++){
for(int j = 0; j < c; j++){
if(mineral[i][j] == '.') continue;
if(visited[i][j]) continue; // ํด๋ฌ์คํฐ์ ์ํ ๋ฏธ๋ค๋์ ๊ฑด๋๋ด๋ค.(์ด๋ฏธ ์ฎ๊ฒจ์ง ๋ฏธ๋ค๋ ํฌํจ)
cluster.clear(); // ์ด๋ฒ ํด๋ฌ์คํฐ๋ฅผ ์ด๊ธฐํํ๋ค.
dfs(i,j); // ํด๋ฌ์คํฐ๋ฅผ ์์ฑํ๋ค.
simulate(); // ํด๋ฌ์คํฐ์ ์ง๋ฉด๊ณผ์ ๊ฑฐ๋ฆฌ๋ฅผ ๊ฐ์ฐํด ํด๋ฌ์คํฐ์ ์์น๋ฅผ ๊ฐฑ์
}
}
}
์ด๋ ์ค๋ ฅ์ ์ํด ๋จ์ด์ง๋ ๋ถ๋ถ์ ๋ค์ ๋ณต์กํ๊ธฐ ๋๋ฌธ์ simulate
ํจ์๋ก ๋ถ๋ฆฌํ๋ค.
void simulate(){
vector<int> low(c,-1); // ํด๋ฌ์คํฐ๋ณ๋ก ๊ฐ๊ฐ์ ์ด์์ ๊ฐ์ฅ ๋ฐ์์๋ ๋ฏธ๋ค๋์ ์์น๋ฅผ ๊ธฐ๋กํ๋ค.
int lowest = r; // ์ด๋ฒ ํด๋ฌ์คํฐ์์ ์ง๋ฉด๊ณผ์ ๊ฐ๊ฒฉ(์ด๊ธฐ๊ฐ์ธ ๊ฐ์ฅ ํฐ๊ฒฝ์ฐ๋ ์ญ์ ์๋ฌด๊ฒ๋ ์๋๊ฒฝ์ฐ ์ง๋ฉด - 0)
for(auto &p : cluster){ // ํด๋ฌ์คํฐ์ ์์๋ค์ ๋ฃจํ๋๋ฆฐ๋ค.
low[p.second] = max(low[p.second], p.first); // ๊ฐ์ฅ ์๋์๋ ํ์ ์ฐพ๋ ์์
mineral[p.first][p.second] = '.'; // ๋ฏธ๋ฆฌ ์ง์๋ฒ๋ฆผ(๊ฐฑ์ ๋ ์์น๋ ํด๋ฌ์คํฐ๋ฅผ ํตํด ์ ์ ์๋ค)
}
for(int j = 0; j < c; j++){
// ์ด๋ฒ ํด๋ฌ์คํฐ์ ํฌํจ๋ ์ด๋ง ํ์ธ(์ด๋ฒ ํด๋ฌ์คํฐ์ ๋ฏธ๋ค๋์ด ์๋ ๊ฒฝ์ฐ -1)
if(low[j] != -1){
int i = low[j];
// ์ง๋ฉด ํน์ ๋ ๋ค๋ฅธ ๋ฏธ๋ค๋์ด ์๋๊ณณ๊น์ง ์ด๋.
while(i < r && mineral[i][j] == '.') i++;
lowest = min(lowest, (i-1)-low[j]); // ๋ ๋ค๋ฅธ ๋ฏธ๋ค๋์ด ์๊ฑฐ๋, ์ง๋ฉด์ธ ๊ฒฝ์ฐ ์ ๊ฐ์ฅ ์๋์ชฝ์ ์๋ ๋ฏธ๋ค๋ ๊ฐ์ ๊ฐ๊ฒฉ
}
}
for(auto &p : cluster){
p.first += lowest; // ํ์ ์์น๋ฅผ ๊ฐ์ฅ ์์ ์ง๋ฉด๊ณผ์ ๊ฐ๊ฒฉ์ ๋ํด ์
๋ฐ์ดํธ
mineral[p.first][p.second] = 'x'; // ํด๋น ์์น๋ก ๋ฐฐ์น
visited[p.first][p.second] = true; // ์ฎ๊ฒจ์ง ๋ฏธ๋ค๋์ ์์น๋ ๋ฐฉ๋ฌธํ๋ค๊ณ ํ์
}
}