Problem 문제풀이
삼성 코테 준비하면서 풀기 적당한 문제 같다. 실수할만한 요소가 꽤 있는 문제이다.
전략
-
좌우 번갈아가면서 막대를 던지는 simulation을 구현한다.
-
공중에 떠 있는 클러스터가 생길 경우 이를 낙하시킨다.
-
남아있는 미네랄을 출력한다.
simulation구현은 매우 간단하다.
void play(int dir, int height)
{
if(dir==0)
{
for (int j = 0; j < C; j++)
{
if (cave[height][j] == 'x')
{
cave[height][j] = '.';
gravity();
break;
}
}
}
else
{
for (int j = C-1; j >= 0; j--)
{
if (cave[height][j] == 'x')
{
cave[height][j] = '.';
gravity();
break;
}
}
}
}
이제 낙하시키는 함수를 구현해보자.
여기서 재밌는 아이디어가 하나 있다. 바닥 층에서만 DFS를 사용하여 미네랄을 탐색하면 어떨까?
바닥에 붙어있는 클러스터는 탐색이 되고 공중에 떠 있는 클러스터는 탐색이 되지 않을 것이다.
그럼 공중에 떠 있는 미네랄들과 바닥 혹은 클러스트와의 거리의 최솟값을 구하여 낙하시키면 된다.
void gravity()
{
for (int i = 0; i < R; i++)
{
for (int j = 0; j < C; j++)
{
visited[i][j] = 0;
}
}
for (int j = 0; j < C; j++)
{
if (visited[R - 1][j] == 0 && cave[R - 1][j] == 'x')
{
dfs(R - 1, j);
}
}
vector<pair<int, int>>floating;
for (int i = 0; i < R; i++)
{
for (int j = 0; j < C; j++)
{
if (cave[i][j] == 'x' && visited[i][j] == 0)
{
floating.push_back({ i,j });
cave[i][j] = '.';
}
}
}
if (floating.empty())
{
return;
}
int minDistance = -1;
for (int i = 0; i < floating.size(); i++)
{
int fi = floating[i].first;
int fj = floating[i].second;
while (fi < R && cave[fi][fj] != 'x')
{
fi++;
}
if (minDistance == -1 || minDistance > fi - floating[i].first -1)
{
minDistance = fi - floating[i].first -1;
}
}
for (int i = 0; i < floating.size(); i++)
{
int fi = floating[i].first;
int fj = floating[i].second;
cave[fi + minDistance][fj] = 'x';
}
floating.clear();
}
void dfs(int row, int col)
{
visited[row][col] = 1;
for (int i = 0; i < 4; i++)
{
int nR = row + dirR[i];
int nC = col + dirC[i];
if (nR >= 0 && nR < R && nC >= 0 && nC < C)
{
if (visited[nR][nC] == 0 && cave[nR][nC] == 'x')
{
dfs(nR, nC);
}
}
}
}
주의해야할 점 몇 가지를 짚고 넘어가자.
-
공중의 클러스트는
.으로 바꾸고 낙하시키는 편이 좋다. 왜 그런지는 잘 생각해보자! -
minDistance는 fi - floating[i].first가 아닌 fi - floating[i].first -1이다.
-
함수가 끝나면 꼭 vector를 clear()해주자. 혹시 모르니까!
이렇게 문제를 한 번 풀어보았다. 두 번 생각해야하는 것이 많을수록 실수가 생기기 쉽다.
주의 또 주의하자. 정확하게 코딩하는 습관을 키우자. 전체 코드를 남기며 마무리한다.
#include <iostream>
#include <vector>
using namespace std;
int R, C, N, H;
int dirR[4] = { 0,1,0,-1 };
int dirC[4] = { 1,0,-1,0 };
char cave[101][101];
int visited[101][101];
void play(int dir, int height);
void print();
void gravity();
void dfs(int row, int col);
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cin >> R >> C;
for (int i = 0; i < R; i++)
{
for (int j = 0; j < C; j++)
{
cin >> cave[i][j];
}
}
cin >> N;
for (int i = 0; i < N; i++)
{
cin >> H;
play(i % 2, R-H);
}
print();
return 0;
}
void play(int dir, int height)
{
if(dir==0)
{
for (int j = 0; j < C; j++)
{
if (cave[height][j] == 'x')
{
cave[height][j] = '.';
gravity();
break;
}
}
}
else
{
for (int j = C-1; j >= 0; j--)
{
if (cave[height][j] == 'x')
{
cave[height][j] = '.';
gravity();
break;
}
}
}
}
void print()
{
for (int i = 0; i < R; i++)
{
for (int j = 0; j < C; j++)
{
cout << cave[i][j];
}
cout << "\n";
}
}
void gravity()
{
for (int i = 0; i < R; i++)
{
for (int j = 0; j < C; j++)
{
visited[i][j] = 0;
}
}
for (int j = 0; j < C; j++)
{
if (visited[R - 1][j] == 0 && cave[R - 1][j] == 'x')
{
dfs(R - 1, j);
}
}
vector<pair<int, int>>floating;
for (int i = 0; i < R; i++)
{
for (int j = 0; j < C; j++)
{
if (cave[i][j] == 'x' && visited[i][j] == 0)
{
floating.push_back({ i,j });
cave[i][j] = '.';
}
}
}
if (floating.empty())
{
return;
}
int minDistance = -1;
for (int i = 0; i < floating.size(); i++)
{
int fi = floating[i].first;
int fj = floating[i].second;
while (fi < R && cave[fi][fj] != 'x')
{
fi++;
}
if (minDistance == -1 || minDistance > fi - floating[i].first -1)
{
minDistance = fi - floating[i].first -1;
}
}
for (int i = 0; i < floating.size(); i++)
{
int fi = floating[i].first;
int fj = floating[i].second;
cave[fi + minDistance][fj] = 'x';
}
floating.clear();
}
void dfs(int row, int col)
{
visited[row][col] = 1;
for (int i = 0; i < 4; i++)
{
int nR = row + dirR[i];
int nC = col + dirC[i];
if (nR >= 0 && nR < R && nC >= 0 && nC < C)
{
if (visited[nR][nC] == 0 && cave[nR][nC] == 'x')
{
dfs(nR, nC);
}
}
}
}