[C++] 백준 20165번: 인내의 도미노 장인 호석

문제 링크

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

문제 요약

높이가 존재하는 도미노가 있다. 이 도미노를 특정한 방향으로 쓰러트리면, 그 방향의 (높이 - 1) 칸의 도미노가 연쇄적으로 쓰러진다.
두 사람 중 한 사람이 R턴 동안 도미노를 쓰러트리고, 나머지 한 사람이 하나를 세우는 걸 번갈아 가며 진행하는 게임을 한다. R턴 동안의 경기 정보가 주어질 때, 쓰러진 도미노의 수를 구해야 한다.

접근 방법

간단한 구현, 시뮬레이션 문제입니다.

도미노의 상태를 저장하는 bool 배열을 선언하고 모두 true로 초기화를 해둡니다. 그리고 높이를 저장하는 별도의 배열도 선언해서 입력을 받아줍니다.

이제 공격자가 도미노를 쓰러트리면 방향을 파악해서 함수를 호출해줍니다. 이 함수는 int값을 반환합니다. 만약, 현재 칸의 도미노가 이미 쓰러진 상태라면 0을 반환합니다.

그렇지 않다면, 쓰러트릴 수 있는 도미노들을 모두 벡터에 기록한 뒤에, 한꺼번에 재귀호출을 해줍니다. 그리고 재귀호출을 통해서 반환된 값들의 합에 1을 더해서 다시 반환해주면 됩니다. 매 턴마다 이 함수를 호출해서 반환된 값을 더해주면 됩니다.

세우는 작업은 그냥 배열의 해당 인덱스의 값을 true로 해주기만 하면 됩니다.

코드

#include <bits/stdc++.h>

using namespace std;

const int MAX = 101;
int n, m, r, b[MAX][MAX], dir[4][2] = { {0, 1}, {0, -1}, {1, 0}, {-1, 0} };
bool stand[MAX][MAX];

int push(int r, int c, int d) {
	if (!stand[r][c])
		return 0;

	stand[r][c] = false;
	int cnt = 1;
	vector<pair<int, int>> v;
	for (int i = 1; i < b[r][c]; i++) {
		int nr = r + dir[d][0] * i;
		int nc = c + dir[d][1] * i;

		if (nr >= 1 && nr <= n && nc >= 1 && nc <= m && stand[nr][nc])
			v.push_back({ nr, nc });
	}

	for (auto& i : v)
		cnt += push(i.first, i.second, d);

	return cnt;
}

int convert(char c) {
	switch (c) {
	case 'E':
		return 0;
	case 'W':
		return 1;
	case 'S':
		return 2;
	case 'N':
		return 3;
	}
}

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	cin >> n >> m >> r;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++)
			cin >> b[i][j], stand[i][j] = true;

	int ans = 0;
	for (int i = 0; i < r; i++) {
		int x, y;
		char d;
		cin >> x >> y >> d;
		ans += push(x, y, convert(d));

		cin >> x >> y;
		stand[x][y] = true;
	}

	cout << ans << '\n';
	
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++)
			cout << (stand[i][j] ? 'S' : 'F') << ' ';
		cout << '\n';
	}

	return 0;
}