안녕하세요, 오늘은 백준 2933번 미네랄 문제를 풀어보겠습니다, 저가 이 문제를 풀게된 계기로는 최근 알고리즘 공부를 많이 하면서 계속 고질적인 문제를 겪고있었는데요, 바로 저가 구현에 엄청 약하다는 문제점을 파악하고 한 동안은 알고리즘 + 빡구현 or 빡구현 문제 위주로 풀어볼려고 합니다,

그리고 오늘 풀어본 문제인 백준 2933번 미네랄 문제 같은 경우에는 위에서 언급한 알고리즘 + 빡구현이 들어간 문제입니다,

문제 파악

우선 문제 파악부터 해보겠읍니다...

위 그림과 같이 우선 막대기를 투척 후 클러스터가 공중에 떠 있으면 그 공중에 뜬 클러스터는 아래로 내려와야합니다. 그리고 이 과정을 정리하면

1. 막대기를 던짐 (이때 왼쪽으로 던지는지 오른쪽으로 던지는지 확인)
2. 막대기로 인해 클러스터가 사라짐
3. 만약 공중에 뜬 클러스터가 있으면 그 클러스터를 아래로 내려줘야 됨
   3.1 먼저 공중에 뜬 클러스터와 바닥에 있는 클러스터의 최상단 부분의 거리를 체크해줘야함
   3.2 체크를 할 때는 공중에 뜬 클러스터의 "열을 기준으로" 가장 아랫부분, 바닥에 있는 클러스터의 가장 최상단 거리를 측정해줘야 함
   3.3 이때 가장 아랫부분이랑 가장 윗부분이 맞닿으면 더이상 클러스터는 밑으로 가지 않기에 다른 클러스터가 겹치는 일은 없음
4. 1번부터 다시 실행

3.2번에 말한 것과 같이 열을 기준으로 바닥과 공중에 있는 클러스터의 거리가 가장 가까운 것을 기준으로
공중에 뜬 클러스터를 내려줘야 됩니다

이처럼 바닥의 클러스터와 맞닿아 있으면 무슨일이 있어도 밑으로 내려가지 않습니다,
마지막 부분 같은 경우엔 오른쪽에서 3번째 행으로 막대기를 던지는데 이렇게 되면 공중에 클러스터가
뜨기 때문에 아래로 내려간 것입니다,

아래는 코드를 작성한 과정입니다.

코드 작성

1.우선 막대기를 던져줍니다.

void stickFun(int x, int th) {
  x = n - x; // 높이 조정
  if (th % 2 == 0) { // 왼쪽으로 던지는 경우
    for (int i = 0; i < m; i++) {
      if (adj[x][i] == 'x') {
        adj[x][i] = '.';
        break;
      }
    }
  } else {
    for (int i = m - 1; i >= 0; i--) {
      if (adj[x][i] == 'x') {
        adj[x][i] = '.';
        break;
      }
    }
  }
}

2. 공중에 뜬 클러스터를 찾습니다

int find_C() {
  int can = 0;

  for (int i = 0; i < n; i++) {
    if (adj[n - 1][i] == 'x' && !visited[n - 1][i]) {
      bfs(n - 1, i);
    }
  }

  for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
      if (adj[i][j] == 'x' && !visited[i][j]) {
        airC.push_back({i, j});
        can = 1;
      }
    }
  }

  return can;
}

이때 바닥에 있는 클러스터를 BFS를 실행해서 방문체크를 해주고
방문체크를 끝내고 나면 n * m 만큼 모든 배열을 순회하여 방문을 안했을 경우, X인 경우는
공중에 뜬 클러스터이므로 따로 벡터에 담아둡니다.

3.클러스터를 아래로 내려줍니다

int move(int x, int y) {
  int cnt = 0;
  for (int i = x + 1; i < n; i++) {
    if (adj[i][y] == 'x') { // 밑에가 클러스터일 경우 
      if (!visited[i][y]) {
        return INF; // 밑에 클러스터가 있음
      } else {
        return cnt;
      }
    } else {
    	cnt++;
	}
  }

  return cnt;
}

void remake() {
  int down = INF;
  for (int i = 0; i < airC.size(); i++) {
    int cnt = move(airC[i].first, airC[i].second);
    down = min(down, cnt);
  }
  if(down == INF) return;
  for(int i = 0; i < airC.size(); i++) {
    int x = airC[i].first;
    int y = airC[i].second;
    adj[x][y] = '.';
  }
  for(int i = 0; i < airC.size(); i++) {
    int x = airC[i].first;
    int y = airC[i].second;
    adj[x + down][y] = 'x';
  }
}

공중에 뜬 클러스터의 갯수만큼 순회를 해줍니다,
이때 x는 행(높이)이므로 x + 1을 함으로써 클러스터 바로 밑에 다른 클러스터가 있는지 또는 빈공간인지 확인해줍니다, 만약 밑에 클러스터가 있으면 INF을 리턴해 다른 공중에 뜬 클러스터를 확인할 수 있습니다,
이때 만약 클러스터가 방문된 경우 바닥에 닿인 클러스터이므로 cnt를 리턴해주고 아래에 X가 아닌 빈 공간이면 cnt++를 통해 카운트를 계속 한 후 가장 down이 작은 만큼 공중에 뜬 클러스터를 아래로 내려줍니다.

4. 1번을 반복합니다

  for(int i = 0; i < stick.size(); i++) {
    visited.clear();
   	visited.resize(n, vector<int>(m, 0)); 
    airC.clear();

    stickFun(stick[i], i);

    if (find_C()) {
      remake();
    }
  }

이떄 visited와 공중에 뜬 클러스터는 계속해서 초기화해주어야 합니다.

코드 길이가 상당해서 앞으로는 구현에 초점을 계속 맞출 거 같습니다,
그리고 만약 빡구현까지 어느정도 능숙해지게 되면 다시 알고리즘 위주로 공부하되
가장 중요한건 밸런스 있게 유동적으로 공부를 이어나가야겠읍니다...

아래는 전체 코드 입니다.

#include <bits/stdc++.h>

using namespace std;

const int INF = 1e9;
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};

int n, m;
int x, y, d;

vector<vector<char>> adj;
vector<pair<int, int>> airC;
vector<vector<int>> visited;
vector<int> stick;

void stickFun(int x, int th) {
  x = n - x; // 높이 조정
  if (th % 2 == 0) { // 왼쪽으로 던지는 경우
    for (int i = 0; i < m; i++) {
      if (adj[x][i] == 'x') {
        adj[x][i] = '.';
        break;
      }
    }
  } else {
    for (int i = m - 1; i >= 0; i--) {
      if (adj[x][i] == 'x') {
        adj[x][i] = '.';
        break;
      }
    }
  }
}

void bfs(int x, int y) {
  queue<pair<int, int>> q;
  q.push({x, y});
  visited[x][y] = 1;

  while (q.size()) {
    int x = q.front().first;
    int y = q.front().second;
    q.pop();

    for (int i = 0; i < 4; i++) {
      int nx = x + dx[i];
      int ny = y + dy[i];
      if (nx < 0 || nx >= n || ny < 0 || ny >= m)
        continue;
      if (!visited[nx][ny] && adj[nx][ny] == 'x') {
        visited[nx][ny] = 1;
        q.push({nx, ny});
      }
    }
  }
}

int find_C() {
  int can = 0;

  for (int i = 0; i < n; i++) {
    if (adj[n - 1][i] == 'x' && !visited[n - 1][i]) {
      bfs(n - 1, i);
    }
  }

  for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
      if (adj[i][j] == 'x' && !visited[i][j]) {
        airC.push_back({i, j});
        can = 1;
      }
    }
  }

  return can;
}

int move(int x, int y) {
  int cnt = 0;
  for (int i = x + 1; i < n; i++) {
    if (adj[i][y] == 'x') { // 밑에가 클러스터일 경우 
      if (!visited[i][y]) {
        return INF; // 밑에 클러스터가 있음
      } else {
        return cnt;
      }
    } else {
    	cnt++;
	}
  }

  return cnt;
}

void remake() {
  int down = INF;
  for (int i = 0; i < airC.size(); i++) {
    int cnt = move(airC[i].first, airC[i].second);
    down = min(down, cnt);
  }
  if(down == INF) return;
  for(int i = 0; i < airC.size(); i++) {
    int x = airC[i].first;
    int y = airC[i].second;
    adj[x][y] = '.';
  }
  for(int i = 0; i < airC.size(); i++) {
    int x = airC[i].first;
    int y = airC[i].second;
    adj[x + down][y] = 'x';
  }
}

int main() {

  cin >> n >> m;

  adj.resize(n, vector<char>(m));

  for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
      cin >> adj[i][j];
    }
  }

  int t;

  cin >> t;
  
  stick.resize(t);

  for (int i = 0; i < t; i++) {
    cin >> stick[i];
  }

  for(int i = 0; i < stick.size(); i++) {
    visited.clear();
   	visited.resize(n, vector<int>(m, 0)); 
    airC.clear();

    stickFun(stick[i], i);

    if (find_C()) {
      remake();
    }
    
      for(int i = 0; i < n; i++) {
    for(int j = 0; j < m; j++) {
      cout << adj[i][j];
    }
    cout << '\n';
  }
    cout << '\n';  cout << '\n';
  }


  return 0;
}