BOJ
BOJ::2933 미네랄
BOJ Gold 3
BOJ::2933 미네랄
- Link : BOJ::2933
- Level : Gold 3
시사점
- 예전에 풀다가 실패했던 문제를 다시 집어들었습니다.
- 매우 좋은 구현문제라고 생각합니다.
- 함수를 구분해야 하는 갯수가 다리만들기2 혹은 나무재테크와 맞먹습니다.
- 구현 문제는 코드가 길어지므로, 작은 실수를 하기 쉬운 것 같습니다.
키
- #미네랄, #막대기, #클러스터
이해(10)
- 문제에 R * C 사이즈의 맵이 주어집니다.
- ’.’은 빈칸, ‘x’는 미네랄이라고 칭합니다.
- 이후, N이 입력되고,
- N개의 숫자가 주어집니다.
- 해당 숫자들은 번갈아가면서 몇번째 행의 좌/우 에서부터 창을 날리는 시뮬레이션을 진행합니다.
- 미네랄이 창을 맞아서 두 개로 분리되는 경우, 공중에 떠 있는 미네랄은 바닥으로 내려와야 합니다.
설계, 손 코딩(25)
- 손으로 중심이 되는 코드를 구현합니다.
- 문제에 명시되어 있는 부분을 정확히할 필요가 있습니다.
- “공중에 떠 있는 미네랄 클러스터는 없으며, 두 개 또는 그 이상의 클러스터가 동시에 떨어지는 경우도 없다.”
- “클러스터가 떨어질 때, 그 클러스터의 맨 아래 부분이 바닥 또는 미네랄 위로 떨어지는 입력만 주어진다.”
- 문제를 해석해보면, 초기에 주어지는 미네랄은 한 덩어리(BFS탐색했을때 한 그룹)이며, 창을 맞고 분리되는 경우 두 덩어리로 분류됩니다.
- 따라서 다음과 같이 설계할 수 있습니다.
- 창을 던집니다.
- 창에 미네랄이 맞은 경우 미네랄을 공백으로 처리해줍니다.
- 바닥행에 있는 미네랄들을 queue에 넣고 BFS를 돌려줍니다.
- BFS로 돌려서 체크한 미네랄의 갯수가 전체 갯수와 맞지 않다면, 두 덩어리로 쪼개졌음을 인식할 수
있습니다.
- 이후, 방문되지 않은 미네랄들을 방문하며 island List에 담습니다.
- 이제 island List에 담긴 공중에 떠 있는 미네랄을 아래로 한칸씩 이동시켜가며 땅 혹은 미네랄과
충돌 하는 순간을 찾습니다.
- 충돌하는 순간 -1 을 하여 미네랄을 이동시킵니다.
시간 복잡도
- findIfThereIsIsland + findIsland :: O(N^2 * 4)
- 두 개의 함수는 따로 동작하지만 visit처리를 하나로 하기 때문에, 합해서 전체 맵을 탐색합니다.
- fallIsland :: O(N^2 * N)
- island의 사이즈가 최대 N^2개일때, N번체크하며 바닥과 충돌하는 경우를 최악으로 생각합니다.
- 물론 실제로는, 사이즈가 클 수록 더 작게 체크할 확률이 높습니다.
공간 복잡도
손 코딩 후 문제 리뷰(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)
- 함수화를 많이 하고 코드가 길어지다 보니 작은 실수들이 시간을 많이 잡아먹었습니다.
- 실수 : over 함수에서 y>C인데, x>C로 사용함.
- 실수 : input 받을때 [1,R+1)인데, [0,R)로 받음.
2nd try
- (2m) : ‘.’과 ‘x’를 0과 1로 생각하고 입력받아 처리하였습니다.
- (3m) : 문제에서 주어지는 창을 던지는 높이는 행이 큰쪽에서부터 작은쪽으로의 카운트이지만, 처리해주지 않았습니다.
- (16m) : move함수에서 분명히, offset을 입력받았지만, x+i로 더해서 처리했습니다.
- offset을 더해서 처리해야했습니다.