백준 2933 미네랄
by 진혀크
문제
창영과 상근은 한 동굴을 놓고 소유권을 주장하고 있다. 두 사람은 막대기를 서로에게 던지는 방법을 이용해 누구의 소유인지를 결정하기로 했다. 싸움은 동굴에서 벌어진다. 동굴에는 미네랄이 저장되어 있으며, 던진 막대기가 미네랄을 파괴할 수도 있다.
동굴은 R행 C열로 나타낼 수 있으며, R×C칸으로 이루어져 있다. 각 칸은 비어있거나 미네랄을 포함하고 있으며, 네 방향 중 하나로 인접한 미네랄이 포함된 두 칸은 같은 클러스터이다.
창영은 동굴의 왼쪽에 서있고, 상근은 오른쪽에 서있다. 두 사람은 턴을 번갈아가며 막대기를 던진다. 막대를 던지기 전에 던질 높이를 정해야 한다. 막대는 땅과 수평을 이루며 날아간다.
막대가 날아가다가 미네랄을 만나면, 그 칸에 있는 미네랄은 모두 파괴되고 막대는 그 자리에서 이동을 멈춘다.
미네랄이 파괴된 이후에 남은 클러스터가 분리될 수도 있다. 새롭게 생성된 클러스터가 떠 있는 경우에는 중력에 의해서 바닥으로 떨어지게 된다. 떨어지는 동안 클러스터의 모양은 변하지 않는다. 클러스터는 다른 클러스터나 땅을 만나기 전까지 게속해서 떨어진다. 클러스터는 다른 클러스터 위에 떨어질 수 있고, 그 이후에는 합쳐지게 된다.
동굴에 있는 미네랄의 모양과 두 사람이 던진 막대의 높이가 주어진다. 모든 막대를 던지고 난 이후에 미네랄 모양을 구하는 프로그램을 작성하시오.
입력
첫째 줄에 동굴의 크기 R과 C가 주어진다. (1 ≤ R,C ≤ 100)
다음 R개 줄에는 C개의 문자가 주어지며, ‘.’는 빈 칸, ‘x’는 미네랄을 나타낸다.
다음 줄에는 막대를 던진 횟수 N이 주어진다. (1 ≤ N ≤ 100)
마지막 줄에는 막대를 던진 높이가 주어지며, 공백으로 구분되어져 있다. 모든 높이는 1과 R사이이며, 높이 1은 행렬의 가장 바닥, R은 가장 위를 의미한다. 첫 번째 막대는 왼쪽에서 오른쪽으로 던졌으며, 두 번째는 오른쪽에서 왼쪽으로, 이와 같은 식으로 번갈아가며 던진다.
공중에 떠 있는 미네랄 클러스터는 없으며, 두 개 또는 그 이상의 클러스터가 동시에 떨어지는 경우도 없다. 클러스터가 떨어질 때, 그 클러스터 각 열의 맨 아래 부분 중 하나가 바닥 또는 미네랄 위로 떨어지는 입력만 주어진다.
출력
- 입력 형식과 같은 형식으로 미네랄 모양을 출력한다.
예제
예제 입력
8 8
........
........
...x.xx.
...xxx..
..xxx...
..x.xxx.
..x...x.
.xxx..x.
5
6 6 4 3 1
예제 출력
........
........
........
........
.....x..
..xxxx..
..xxx.x.
..xxxxx.
접근
- 1일차 : 미네랄이 사라진 곳을 기점으로 BFS를 실행하여 바닥에 있는 클러스터와 하늘에 있는 클러스터를 구분했다.
- 각 열의 맨 아래 부분 중 하나가 바닥 또는 미네랄 위로 떨어진다는 것을 무조건 맨 아래 부분이 닿는 것인줄 알고 클러스터를 구분 할 때 맨 아래 부분을 저장해놨다가 그 곳을 기점으로 떨어질 거리를 계산했는데 실패했다. 그대로 각 열의 맨 아래 부분 중 ‘하나’가 닿는 것이었는데 잘못된 해석을 했다. 계속 11%에서 실패했습니다가 떴다..!
- 2일차 : 입력의 조건에 다시 한 번 집중했다. 두 개 또는 그 이상의 클러스터가 동시에 떨어지는 경우가 없다 + 바닥 또는 미네랄 위로 떨어지는 입력만 주어진다 라는 조건에 집중했다.
- 공중에 떠 있는 클러스터는 하나 뿐이므로 바닥에 있는 미네랄을 기점으로 BFS를 실행 한 후 BFS를 실행하며 count한 미네랄의 갯수가 전체 미네랄의 갯수와 일치하면 변화가 필요없는 것이고 더 적으면 공중에 떠 있는 클러스터가 있다고 판단했다.
내가 생각한 풀이
- 클러스터가 분리 된 경우와 그렇지 않은 경우를 구분하자.
- 공중에 떠있는 경우와 그렇지 않은 경우를 구분하자. (맨 아래 칸에 있는 미네랄이 삭제 될 경우 클러스터가 분리 되지 않더라도 공중에 떠 있는 경우가 생긴다.)
미처 생각하지 못했던것
- 문제를 제대로 해석도 하지 않은 채로 문제 풀이를 시작했던 것이 가장 큰 실수였다. 사소한 실수 때문에 하루가 넘는 시간동안 고민했다. 문제를 잘 읽자. 닥치는대로 구현하지 말고 해야 할 일을 차근차근 정리한 후 문제를 풀자.
코드
#include<iostream>
#include<queue>
#include<vector>
#include<cstring>
using namespace std;
int R, C, mineral = 0, d[4][2] = {{1,0},{-1,0},{0,1},{0,-1}};
char map[101][101] = {};
vector<int> input_v;
int check[101][101] = {0, };
//todo : input 받기
void input()
{
int N, temp;
cin>>R>>C;
for(int i = 1 ; i<=R ; i++)
{
for(int j = 1 ; j<=C ; j++)
{
cin>>map[i][j];
if(map[i][j] == 'x') mineral++;
}
}
cin>>N;
for(int i = 0 ; i<N ;i++)
{
cin>>temp;
input_v.push_back(temp);
}
}
//todo : map밖으로 나가지 않게 범위 측정
bool check_bound(int y, int x)
{
return (y>0 && y<=R && x>0 && x<=C);
}
//todo : 왼쪽 오른쪽 구분하여 미네랄 제거, 제거 할 미네랄 없을 시도 고려
bool crash(int h, int n)//h는 높이, n은 홀수 짝수 구분, h를 넣을 때 R-h로 넣어줘야 함.
{
bool flag = 0;
if(n%2 == 0)//왼쪽 부수는 경우
{
for(int i = 1 ; i<=C ; i++)
{
if(map[h][i] == 'x')
{
map[h][i] = '.';
flag = 1;
mineral--;
break;
}
}
}
else//오른쪽 부수는 경우
{
for(int i = C ; i>0 ; i--)
{
if(map[h][i] == 'x')
{
map[h][i] = '.';
flag = 1;
mineral--;
break;
}
}
}
return flag; //flag가 1이면 부숴진 것, 아니면 안 부숴진 것
}
void print_map()
{
for(int i = 1 ; i<=R ; i++)
{
for(int j = 1 ; j<=C ; j++)
cout<<map[i][j];
cout<<'\n';
}
}
//todo : 클러스터 찾아낸 후 공중에 떠 있는 클러스터 아래로 내리기
bool floor_BFS() //공중에 떠 있는 클러스터가 있는지 확인
{
memset(check, 0, sizeof(check));
int temp_mineral = 0;
queue<pair<int, int>> q;
for(int i = 1 ; i<=C ; i++) //바닥을 돌며 BFS 실행
{
if(map[R][i] == 'x')
{
q.push({R,i});
}
}
while(!q.empty())
{
pair<int, int> t = q.front();
q.pop();
temp_mineral++;
check[t.first][t.second] = 1;
for(int i = 0 ; i<4 ; i++)
{
int nextY = t.first + d[i][0], nextX = t.second + d[i][1];
if(check_bound(nextY, nextX) && !check[nextY][nextX] && map[nextY][nextX] == 'x')
{
q.push({nextY, nextX});
check[nextY][nextX] = 1;
}
}
}
if(temp_mineral == mineral)
{
return 0;
}
for(int i = 1 ; i<=R ; i++)
{
for(int j = 1 ; j<=C ; j++)
{
if(map[i][j] == 'x' && check[i][j] == 0)
{
q.push({i,j});
break;
}
}
}
while(!q.empty())
{
pair<int, int> t = q.front();
q.pop();
check[t.first][t.second] = 2;
for(int i = 0 ; i<4 ; i++)
{
int nextY = t.first + d[i][0], nextX = t.second + d[i][1];
if(check_bound(nextY, nextX) && !check[nextY][nextX] && map[nextY][nextX] == 'x')
{
q.push({nextY, nextX});
check[nextY][nextX] = 2;
}
}
}
return 1;
}
int check_Distance(int y, int x)
{
int distance = 0;
for(int i = y+1 ; i<=R ; i++)
{
if(check[i][x] == 2) //아래쪽에 클러스터의 일부분이 존재하는 경우 처리할 필요 없음.
{
return 1000;
}
if(check[i][x] == 0) distance++; //비어있는 경우 거리 증가
if(check[i][x] == 1) return distance; //떠있는 클러스터가 아닌 다른 클러스터를 만나면 return;
}
return distance; //바닥에 닿으면 return
}
void drop_Cluster()
{
//todo : 떨어져야 할 거리 측정
int drop_distance = 1000;
for(int i = R ; i>0 ; i--)
{
for(int j = 1 ; j<=C ; j++)
{
if(check[i][j] == 2)
{
int temp_distance = check_Distance(i,j);
drop_distance = min(drop_distance, temp_distance); //최소 값을 찾아서 넣어준다.
}
}
}
//todo : 클러스터 떨구기
for(int i = R ; i>0 ; i--)
{
for(int j = 1 ; j<=C ; j++)
{
if(check[i][j] == 2)
{
map[i][j] = '.';
map[i+drop_distance][j] = 'x';
}
}
}
}
int main(void)
{
input();
for(int i = 0 ; i<input_v.size() ; i++)
{
bool tf;
tf = crash(R-input_v[i]+1, i);
if(!tf) continue;
tf = floor_BFS();
if(!tf) continue;
drop_Cluster();
}
print_map();
return 0;
}
Subscribe via RSS