BOJ::2933 미네랄

시사점

이해(10)

설계, 손 코딩(25)

시간 복잡도

공간 복잡도

손 코딩 후 문제 리뷰(x)

구현(35)

함수 List

// 범위를 체크합니다.
bool over(int x, int y);

// 좌측, 우측에서 창을 날려서 맞는 미네랄이 있다면 제거합니다.
// 제거된 미네랄로 인해 전체 클러스터가 2개로 분리되었다면, 공중에 떠 있는 미네랄을 떨어뜨려 줍니다.
void simulate(bool who, int row);

// 바닥행에서부터 BFS를 출발시켜서 전체 미네랄을 탐색했는지 확인합니다.
// 전체미네랄이 count되었다면 false를, 그렇지 않다면 true를 반환합니다.
bool findIfThereIsIsland();

// 분리된 island를 List에 담습니다
void findIsland();

// 분리된 CLUSTER를 바닥으로 한칸씩 떨어뜨리며, 충돌하는지 체크합니다.
// 충돌시 해당 offset-1값에 대해 맵에 업데이트 합니다.
void fallIsland();

업데이트 되는 변수

// 업데이트 되는 변수 -----------------------------------------
int totalMNL, partialMNL; // 전체 mineral의 갯수, 체크한 mineral의 갯수 입니다.
char a[MAXRC][MAXRC]; // 매우 빈번히 업데이트 되는 변수입니다.
bool visited[MAXRC][MAXRC]; // 공중에 떠 있는 클러스터가 존재하는지 찾는 bfs에서 사용됩니다.
vector<pair<int,int> > island; // 공중에 떠 있는 클러스터의 목록을 갖습니다.
queue<pair<int, int> > q; // bfs에 사용됩니다.
// 업데이트 되는 변수 -----------------------------------------

실제 구현

// 실수 : over 함수에서 y>C인데, x>C로 사용함.
// 실수 : input 받을때 [1,R+1)인데, [0,R)로 받음.
#include<bits/stdc++.h>
#define bottom R
#define rep(i,a,b) for(int i=a;i<b;i++)
#define r_rep(i,a,b) for(int i=a;i>b;i--)
const int MAXRC = 100+1;
const int dx[]={-1, 0, 1, 0}, dy[]={0, 1, 0, -1};
using namespace std;

int R, C, N;
// 업데이트 되는 변수 -----------------------------------------
int totalMNL, partialMNL; // 전체 mineral의 갯수, 체크한 mineral의 갯수 입니다.
char a[MAXRC][MAXRC]; // 매우 빈번히 업데이트 되는 변수입니다.
bool visited[MAXRC][MAXRC]; // 공중에 떠 있는 클러스터가 존재하는지 찾는 bfs에서 사용됩니다.
vector<pair<int,int> > island; // 공중에 떠 있는 클러스터의 목록을 갖습니다.
queue<pair<int, int> > q; // bfs에 사용됩니다.
// 업데이트 되는 변수 -----------------------------------------
// 범위를 체크합니다.
bool over(int x, int y){return (x<1 || y<1 || x>R || y>C);}

// bfs를 진행합니다.
// 바닥면에서부터 올라오는 bfs라면 매개변수의 값이 flase
// 분리된 클러스터에 대한 bfs라면 매개변수의 값이 true입니다.
void bfs(bool isIsland){
    while(!q.empty()){
        int x = q.front().first, y = q.front().second; q.pop();
        if(isIsland){
            island.push_back({x, y});
            a[x][y] = '.';
        }
        rep(i, 0, 4){
            int nx = x+dx[i], ny = y+dy[i];
            if(over(nx, ny) || visited[nx][ny] || a[nx][ny] =='.') continue;
            q.push({nx, ny});
            visited[nx][ny] = true;
            if(!isIsland) partialMNL++;
        }
    }
}

// 바닥행에서부터 BFS를 출발시켜서 전체 미네랄을 탐색했는지 확인합니다.
// 전체미네랄이 count되었다면 false를, 그렇지 않다면 true를 반환합니다.
bool findIfThereIsIsland(){
    partialMNL = 0;
    rep(j, 1, C+1){
        if(a[bottom][j] == 'x'){
            q.push({bottom, j});
            visited[bottom][j] = true;
            partialMNL++;
        }
    }
    bfs(false);
    if(totalMNL > partialMNL) return true;
    return false;
}

// 분리된 island를 List에 담습니다
void findIsland(){
    rep(i, 1, R+1){
        rep(j, 1, C+1){
            if(a[i][j] == 'x' && visited[i][j] == false){
                q.push({i, j});
                visited[i][j] = true;
            }
        }
    }
    bfs(true);
}

// 분리된 CLUSTER를 바닥으로 한칸씩 떨어뜨리며, 충돌하는지 체크합니다.
// 충돌시 해당 offset-1값에 대해 맵에 업데이트 합니다.
void fallIsland(){
    int offset = 0;
    bool touchedMNL = false, touchedBottom = false;
    rep(add, 1, R+1){
        rep(i, 0, (int)island.size()){
            int x = island[i].first, y = island[i].second;
            if(x+add > R){ // 대소비교 : 같다는 포함안되는게 맞는 듯
                touchedBottom = true;
                break;
            }
            if(a[x+add][y] == 'x'){
                touchedMNL = true;
                break;
            }
        }
        if(touchedMNL || touchedBottom){
            offset = add-1;
            break;
        }
    }
    // update List to Map
    rep(i, 0, (int)island.size()){
        int x = island[i].first, y = island[i].second;
        if(a[x+offset][y] == 'x') cout << "SOMETHINGS WRONG" <<'\n';
        a[x+offset][y] = 'x';
    }
}

// 좌측, 우측에서 창을 날려서 맞는 미네랄이 있다면 제거합니다.
// 제거된 미네랄로 인해 전체 클러스터가 2개로 분리되었다면, 공중에 떠 있는 미네랄을 떨어뜨려 줍니다.
void simulate(bool who, int row){
    bool found = false;
    // Left
    if(who == false){
        rep(j, 1, C+1) if(a[row][j] == 'x'){
            found = true;
            a[row][j] = '.';
            totalMNL -= 1;
            break;
        }
    }else{
        r_rep(j, C, 0) if(a[row][j] == 'x'){
            found = true;
            a[row][j] = '.';
            totalMNL -= 1;
            break;
        }
    }
    // 제거된 미네랄이 있다면
    if(found){
        memset(visited, false, sizeof(visited));
        // 분리된 미네랄이 있다면
        if(findIfThereIsIsland()){
            island.clear();
            findIsland();
            if(totalMNL != partialMNL + (int)island.size()) cout << "SOMETHINGS WRONG" <<'\n';
            fallIsland();
        }
    }
}

void PRINT(){
    rep(i, 1, R+1){
        rep(j, 1, C+1){
            cout << a[i][j];
        }cout<<'\n';
    }
}

int main(){
    freopen("input.txt", "r", stdin);
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> R >> C;
    rep(i, 1, R+1) rep(j, 1, C+1){
        cin >> a[i][j];
        if(a[i][j] == 'x') totalMNL++;
    }
    cin >> N;
    rep(i, 0, N){
        int row;
        cin >> row;
        simulate(i%2, R-row+1);
    }
    PRINT();
    return 0;
}
2nd try(49m)
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<b;i++)
#define r_rep(i,a,b) for(int i=a;i>b;i--)
const int MAXNM = 100;
const int dx[]={-1, 0, 1, 0}, dy[]={0, 1, 0, -1};
using namespace std;

int n, m, allx;
char a[MAXNM][MAXNM];
bool seen[MAXNM][MAXNM];
queue<pair<int,int> > q;
void input(){
    cin >> n >> m;
    rep(i, 0, n) rep(j, 0, m){
        cin >> a[i][j];
        if(a[i][j] == 'x') allx++;
    }
}
bool project(int r, bool who){
    if(!who){
        rep(j, 0, m) if(a[r][j] == 'x'){
            a[r][j] = '.'; // 실수(2) : 0으로 초기화함
            return true;
        }
    }else{
        r_rep(j, m-1, -1) if(a[r][j] == 'x'){
            a[r][j] = '.';
            return true;
        }
    }
    return false;
}
bool over(int x, int y){ return (x<0 || y<0 || x>=n || y>=m);}
int countFromBottom(){
    memset(seen, false, sizeof(seen));
    int cnt = 0;
    rep(j, 0, m) if(a[n-1][j] == 'x'){
        q.push({n-1, j});
        seen[n-1][j] = true;
    }
    while(!q.empty()){
        int x = q.front().first, y = q.front().second; q.pop();
        cnt++;
        rep(i, 0, 4){
            int nx = x+dx[i], ny = y+dy[i];
            if(over(nx, ny) || seen[nx][ny] || a[nx][ny] == '.') continue;
            seen[nx][ny] = true;
            q.push({nx, ny});
        }
    }
    return cnt;
}
vector<pair<int,int> > findSeparated(){
    vector<pair<int,int> > ret;
    rep(i, 0, n) rep(j, 0, m) if(a[i][j] == 'x' && !seen[i][j]){
        seen[i][j] = true;
        ret.push_back({i, j});
        a[i][j] = '.';
    }
    return ret;
}
int findOffset(vector<pair<int,int> >& v){
    int ret = 0;
    rep(i, 1, n){
        rep(j, 0, v.size()){
            int x = v[j].first, y = v[j].second;
            if(x+i == n || a[x+i][y] == 'x'){
                return i-1;
            }
        }
    }
    return ret;
}
void move(int offset, vector<pair<int,int> >& v){
    rep(i, 0, v.size()){
        int x = v[i].first, y = v[i].second;
        a[x+offset][y] = 'x'; // 실수(16)offset 더해야 하는데 i를 더함
    }
}
void PRINT(){
    rep(i, 0, n){
        rep(j, 0, m){
            cout << a[i][j];
        }cout << endl;
    }
}
void process(){
    input();
    int games, r;
    cin >> games;
    rep(rnd, 0, games){
        cin >> r; r = n - r; // 실수(3) : 위아래 바꾸는 것, 처리 안 해줌
        // projecting sword
        if(!project(r, rnd%2)) continue;
        allx--;

        // counting a cluster
        int cnt = countFromBottom();

        // counting floating cluster if it's exists
        if(allx == cnt) continue;
        vector<pair<int,int> > spr = findSeparated();

        // chekcing the offset to connect a cluster
        int shifts = findOffset(spr);
        move(shifts, spr);
    }
    PRINT();
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    process();
    return 0;
}

구현 후 코드리뷰 + 예제 돌려보기(7)

디버깅(20)

2nd try

  • (2m) : ‘.’과 ‘x’를 0과 1로 생각하고 입력받아 처리하였습니다.
  • (3m) : 문제에서 주어지는 창을 던지는 높이는 행이 큰쪽에서부터 작은쪽으로의 카운트이지만, 처리해주지 않았습니다.
  • (16m) : move함수에서 분명히, offset을 입력받았지만, x+i로 더해서 처리했습니다.
    • offset을 더해서 처리해야했습니다.

좋은 코드

최적화