์๊ณ ๋ฆฌ์ฆ
- 2933 ๋ฏธ๋ค๋๊ณผ ์๋นํ ์ ์ฌํ ๋ฌธ์ ์ด์ง๋ง, โ๋ถ๋ฆฌ๋ ํด๋ฌ์คํฐ์ ๊ฐ ์ด์ค ๋งจ ์๋ ๋ถ๋ถ์ด ์๋ ๋ถ๋ถ์ด ๋ค๋ฅธ ํด๋ฌ์คํฐ ์์ ๋จ์ด์ง ์ ์๋คโ๋ผ๋ ์กฐ๊ฑด์ ํ๋ ๋ ์๊ฐํด์ผํจ.
- ๋ง๋๋ฅผ ๋์ง๊ณ ํด๋ฌ์คํฐ๊ฐ ๋ถ๋ฆฌ๋๋ฉด ๋ฐ๋ฅ์ ๋ฟ์๋์ง ํ๋จ.
- ๋ฟ์ง ์์๋ค๋ฉด ์๋๋ก ๋ด๋ฆฌ๋๋ฐ, ๋ด๋ ค๊ฐ ์ ์๋ ๋ฏธ๋ค๋์ ๋ค ๊ฒ์ฌ.
- ๊ฐ์ฅ ์ ๊ฒ ๋ด๋ ค๊ฐ ์ ์๋ ๊ฑฐ๋ฆฌ๋งํผ ํด๋ฌ์คํฐ๋ฅผ ๋ด๋ฆผ.
์ฝ๋
#include <iostream>
#include <list>
#include <algorithm>
using namespace std;
int R, C, listIdx;
char map[101][101];
int offset[4][2] = { {-1, 0}, {0,1}, {1, 0}, {0, -1} };
bool visit[101][101];
pair<int, int> l[10010];
void throwStick(int h, bool toRight);
bool isTouchFloor(int h, int w);
void downCluster();
int main() {
string t;
cin >> R >> C;
for (int i = 0; i < R; i++) {
cin >> t;
for (int j = 0; j < C; j++) {
map[i][j] = t[j];
}
}
int n, input;
bool toRight = true;
cin >> n;
while (n--) {
cin >> input;
throwStick(input, toRight);
toRight = !toRight;
}
for (int i = 0; i < R; i++) {
for (int j = 0; j < C; j++)
cout << map[i][j];
cout << endl;
}
}
// ๋์ง๊ณ ๋ง์ผ๋ฉด, ๋ง์ ๊ฑฐ๋ถํฐ ์ํ์ข์ฐ ๊ฒ์ํ์ฌ ํด๋ฌ์คํฐ ์ฐพ๊ณ ๋ด๋ฆฌ๊ธฐ.
void throwStick(int h, bool toRight) {
bool hit = false;
int w = 0;
h = R - h;
if (toRight) {
for (int i = 0; i < C; i++)
if (map[h][i] == 'x') {
hit = true;
w = i;
break;
}
}
else {
for (int i = C - 1; i >= 0; i--)
if (map[h][i] == 'x') {
hit = true;
w = i;
break;
}
}
if (!hit)
return;
map[h][w] = '.';
for (int i = 0; i < 4; i++) {
int ho = h + offset[i][0], wo = w + offset[i][1];
if (ho >= 0 && ho < R && wo >= 0 && wo < C && map[ho][wo] == 'x') {
if (!isTouchFloor(ho, wo))
downCluster();
for (int i = 0; i < listIdx; i++)
visit[l[i].first][l[i].second] = false;
listIdx = 0;
}
}
}
bool isTouchFloor(int h, int w) {
int curIdx = 0;
listIdx = 0;
l[listIdx++] = { h,w };
visit[h][w] = true;
bool touch = false;
while (curIdx != listIdx) {
int h = l[curIdx].first, w=l[curIdx].second;
curIdx++;
if (h == R - 1) {
touch = true;
break;
}
for (int i = 0; i < 4; i++) {
int ho = h + offset[i][0], wo = w + offset[i][1];
if (!visit[ho][wo] && ho >= 0 && ho < R && wo >= 0 && wo < C && map[ho][wo] == 'x') {
l[listIdx++] = { ho, wo };
visit[ho][wo] = true;
}
}
}
if (touch)
return true;
return false;
}
//๋ฐ์ ๋ด๊ฒ ์๋ ๊ฒ๋ง ๊ฒ์ฌ -> ๋ช์นธ ๋ด๋ ค๊ฐ๋ฉด ๋๋์ง ์ถ์ฐํ๊ธฐ
void downCluster() {
sort(&l[0], &l[listIdx]);
int minDistance = 2000000000;
for (int s = listIdx - 1; s >= 0; s--) {
if (map[l[s].first + 1][l[s].second] != 'x') {
int fromH = l[s].first + 1;
for (; fromH < R; fromH++) {
if (map[fromH][l[s].second] == 'x') {
if (visit[fromH][l[s].second])
fromH = 2000000000;
break;
}
}
minDistance = min(minDistance, fromH - l[s].first -1);
}
}
for (int s = listIdx - 1; s >= 0; s--) {
map[l[s].first + minDistance][l[s].second] = 'x';
map[l[s].first][l[s].second] = '.';
}
}