[백준 20165] 인내의 도미노 장인 호석

문제

www.acmicpc.net/problem/20165

20165번: 인내의 도미노 장인 호석

 

풀이

문제에서 주어진 진행방식을 읽고, 아래를 생각하면서 구현하면 어렵지 않게 구현할 수 있습니다.

 

1. 한 도미노가 엎어질 때, 서있는 다른 도미노가 같은 방식으로 엎어지므로 "엎어진 도미노의 개수를 반환"하는 함수를 작성해 쓰러진 도미노의 개수를 셀 수 있습니다.

 

2. 길이가 K인 도미노가 넘어져 K - 1개의 도미노가 쓰러질 때, 이미 쓰러져있는 도미노는 영향을 받지 않습니다. 따라서 도미노가 쓰러지는 부분을 구현할 때, 새로 쓰러진 도미노의 개수만 카운트하며 그 도미노들이 엎어져 다른 도미노에 영향을 준다고 생각하면 됩니다.

 

코드

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;

const int dir[4][2] = {
	{ -1,0 },{ 1,0 },{ 0,-1 },{ 0,1 }
};
int n, m, R, x, y, nr, nc, ans, di, g[101][101];
char d, cmd;
bool isok[101][101];

int go(int r, int c, char d, int l) {
	queue<pii> q;
	int ret = 0;
	if (d == 'E') di = 3;
	else if (d == 'W') di = 2;
	else if (d == 'S') di = 1;
	else di = 0;
	for (int i = 0; i < l; i++) {
		nr = r + dir[di][0] * i, nc = c + dir[di][1] * i;
		if (nr < 0 || nc < 0 || nr >= n || nc >= m) continue;
		if (isok[nr][nc]) {
			if (i > 0) q.push({ nr,nc });
			isok[nr][nc] = 0, ret++;
		}
	}
	while (!q.empty()) {
		tie(nr, nc) = q.front(); q.pop();
		ret += go(nr, nc, d, g[nr][nc]);
	}
	return ret;
}

int main() {
	cin.tie(NULL); cout.tie(NULL);
	ios_base::sync_with_stdio(false);

	cin >> n >> m >> R;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
			cin >> g[i][j], isok[i][j] = 1;

	for (int i = 0; i < R; i++) {
		cin >> x >> y >> cmd;
		x--, y--;
		ans += go(x, y, cmd, g[x][y]); // (x, y)도미노를 cmd방향으로 넘어뜨릴 때, 엎어진 도미노의 개수
		cin >> x >> y;
		x--, y--;
		if (!isok[x][y]) isok[x][y] = 1; // (x, y)도미노를 다시 세움
	}
	cout << ans << '\n';
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++)
			cout << (isok[i][j] ? "S " : "F ");
		cout << '\n';
	}
}