๋ฏธ๋„ค๋ž„(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; // ์˜ฎ๊ฒจ์ง„ ๋ฏธ๋„ค๋ž„์˜ ์œ„์น˜๋„ ๋ฐฉ๋ฌธํ–ˆ๋‹ค๊ณ  ํ‘œ์‹œ
  }
}