์•Œ๊ณ ๋ฆฌ์ฆ˜

  • 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] = '.';
	}
}