푸키키키

문제 링크

• https://www.acmicpc.net/problem/2933

풀이

eraseBlock();
rootedClusterCheck();
flyClusterDown();

eraseBlock();

왼쪽, 오른쪽에서 막대기를 던질 때 해당하는 block을 제거하는 로직.

rootedClusterCheck();

rooted → 땅에 박혀있는 이라는 의미로 변수명 지었다. 땅(row == 0) 까지 연결되어 있는 클러스터는 땅으로 떨어지지 않기 때문에 먼저 땅과 연결되어 있는 클러스터들을 체크해줬다.

체크한 방법은 row == 0에 있는 것 중에서 x가 있으면 그걸 시작점으로 dfs를 돌면서 연결되어 있는 것들을 체크했다.

flyClusterDown();

앞에서 땅과 연결되어 있는 클러스터들은 체크가 됐다. 그렇다면 입력 테이블에서 'x'이면서 땅과 연결된 클러스터로 체크되지 않은 것은 모두 공중에 있는 클러스터일 것이다. 문제조건에 두 개 이상의 클러스터는 공중에 있지 않다고 했으므로 해당하는 x를 만나면 거기서 dfs를 통해 공중에 있는 클러스터들을 체크해줬다.

그리고 이 클러스터를 땅이나 만나는 미네랄에 연결시켜줘야 한다. 이 클러스터는 전체적으로 똑같은 col만큼 아래로 하강하는데 이 값을 효율적으로 구하기 위해 dfs돌면서 각 column의 가장 작은 row값을 따로 저장해 뒀다.

int findDownLength() {
  int minLength = 9999999;
  for(int j=0;j<c;++j) {
    if(columnList[j] == 999999) continue;
    for(int i=0;i<r;++i) {
      if(table[i][j] == 'x') {
        if(i == columnList[j]) {
          minLength = min(minLength, i);
          break;
        } else {
          minLength = min(columnList[j] - i - 1, minLength);
        }
      }
    }
  }
  return minLength;
}

이 값들은 위와 같은 코드에 사용되는데 땅부터 row를 증가시키면서 찾다가 테이블에 'x'를 만났다면 두 가지 경우중 하나이다.

첫 번째는 공중에 떠있는 자기자신을 만났을 때,

두 번째는 다른 땅과 연결된 클러스터를 만났을 때이다.

전자는 자기를 만났기 때문에 자기 위쪽은 탐색할 필요 없다. 그래서 클러스터를 몇칸 땅으로 이동시킬지에 대한 변수인 minLength를 자기 row값으로 min(minLength, i)로 최신화 시켜주었다.

후자는 지금 만난 x보다 더 위에도 x가 존재할 수 있고, 그 때에는 minLength가 더 작아지기 때문에 추가적인 탐색이 필요해 break를 걸지 않았다.

이렇게 몇칸 아래로 내릴지 구한다음 공중에 떠있는 클러스터들은 모두 체크가 되어 있기 때문에 그 칸만큼 내려준다.

이 3가지 과정을 N번 진행하면 문제가 풀린다.

코드

#include <iostream>
#include <vector>

using namespace std;

char table[101][101];

int r, c;
bool isrootedCluster[101][101];
void rootedClusterClear() {
  for(int i=0;i<r;++i) {
    for(int j=0;j<c;++j) {
      isrootedCluster[i][j] = false;
    }
  }
}

vector<int> stickThrowRow;

void input() {
  cin >> r >> c;
  for(int i=0;i<r;++i) {
    for(int j=0;j<c;++j) {
      cin >> table[r-i-1][j];
    }
  }
  int n;
  cin >> n;
  int temp;
  for(int i=0;i<n;++i) {
    cin >> temp;
    stickThrowRow.push_back(temp); 
  }
}

bool blockErase(int row, int col) {
  if(table[row][col] == 'x') {
    table[row][col] = '.';
    return true;
  }
  return false;
}

void eraseBlock(int throwIdx, bool isRightToLeft) {
  if(isRightToLeft) {
    for(int i=0;i<c;++i) {
      if(blockErase(throwIdx, i)) return;
    }
  } else {
    for(int i=c-1;i>=0;--i) {
      if(blockErase(throwIdx, i)) return;
    }
  }
}

int dx[] = {0,0,1,-1};
int dy[] = {1,-1,0,0};
bool dfsRangeChk(int nx, int ny) {
  return (0 <= nx && nx < c && 0 <= ny && ny < r);
}

bool dfsVisited[101][101];
void dfsVisitedClear() {
  for(int i=0;i<r;++i) {
    for(int j=0;j<c;++j) {
      dfsVisited[i][j] = false;
    }
  }
}

bool columnCheckNeeded = false;
int columnList[101];
void clearColumnList() {
  for(int i=0;i<101;++i) {
    columnList[i] = 999999;
  }
}

void dfs(int row, int col) {
  for(int i=0;i<4;++i) {
    int nx = col + dx[i];
    int ny = row + dy[i];
    if(dfsVisited[ny][nx] == false && dfsRangeChk(nx, ny)) {
      if(table[ny][nx] == 'x'){
        if(columnCheckNeeded) {
          columnList[nx] = min(columnList[nx], ny);
        }
        dfsVisited[ny][nx] = true;
        dfs(ny, nx);
      }
    }
  }
}

void pasteRootedResult() {
  for(int i=0;i<r;++i) {
    for(int j=0;j<c;++j) {
      if(dfsVisited[i][j] == true) {
        isrootedCluster[i][j] = true;
      }
    }
  }
}

void rootedClusterCheck() {
  for(int i=0;i<c;++i) {
    if(isrootedCluster[0][i] == false && table[0][i] == 'x') {
      dfsVisitedClear();
      isrootedCluster[0][i] = true;
      dfs(0, i);
      pasteRootedResult();
    } 
  }
}

void findflyCluster(int i, int j) {
  dfsVisitedClear();
  dfsVisited[i][j] = true;
  columnList[j] = i;
  dfs(i, j);
}

int findDownLength() {
  int minLength = 9999999;
  for(int j=0;j<c;++j) {
    if(columnList[j] == 999999) continue;
    for(int i=0;i<r;++i) {
      if(table[i][j] == 'x') {
        if(i == columnList[j]) {
          minLength = min(minLength, i);
          break;
        } else {
          minLength = min(columnList[j] - i - 1, minLength);
        }
      }
    }
  }
  return minLength;
}

void downCluster() {
  int downLength = findDownLength();
  for (int j = 0; j < c; ++j) {
    for (int i = 0; i < r; ++i) {
      if(dfsVisited[i][j] == true) {
        table[i][j] = '.';
        table[i-downLength][j] = 'x';
      }
    }
  }
}

void flyClusterDown() {
  for(int i=0;i<r;++i) {
    for(int j=0;j<c;++j){
      if(isrootedCluster[i][j] == false && table[i][j] == 'x') {
        clearColumnList();
        columnCheckNeeded = true;
        findflyCluster(i, j);
        columnCheckNeeded = false;
        downCluster();
        return;
      }
    }
  }
}

void processing() {
  for(int i=0;i<stickThrowRow.size(); ++i) {
    eraseBlock(stickThrowRow[i]-1, i%2==0);
    rootedClusterCheck();
    flyClusterDown();
    rootedClusterClear();
  }
}

void printAnswer() {
  for(int i=0;i<r;++i) {
    for(int j=0;j<c;++j) {
      cout << table[r-i-1][j];
    }
    cout << '\n';
  }
}

int main(void) {
  // freopen("b2933.txt", "r", stdin);
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  input();
  processing();
  printAnswer();
}

boj.kr/5567