백준 20165번 인내의 도미노 장인 호석 문제풀이(C++)

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

아이디어

조건

1. 공격수는 특정 격자에 놓인 도미노를 동, 서, 남, 북 중 원하는 방향으로 넘어뜨린다.
   길이가 K인 도미노가 특정 방향으로 넘어진다면, 그 방향으로 K-1 개의 도미노들 중에 아직 넘어지지 않은 것들이 같은 방향으로 연달아 넘어진다.
   이 때, 당연히 도미노의 특성상, 연쇄적으로 도미노가 넘어질 수 있다.
   ※이미 넘어진 도미노가 있는 칸을 공격한 경우에는 아무 일이 일어나지 않는다.

조건 구현

1 - 1 동서남북 원하는 방향을 구하기

// Direction : E, W, S, N
constexpr int d_row[] = { 0,0,1,-1 };
constexpr int d_col[] = { 1,-1,0,0 };
// ---
int select_direction(const int attack_direction)
{
	switch (attack_direction)
	{
	case 'E': return 0;
	case 'W': return 1;
	case 'S': return 2;
	case 'N': return 3;
	default:;
	}
	return -1; // error
}

 

1 - 2 길이가 K인 도미노가 특정 방향으로 넘어진다면, 그 방향으로 K-1 개의 도미노들 중에 아직 넘어지지 않은 것들이 같은 방향으로 연달아 넘어진다.

// Variable(queue): for storing the next state
	queue<statement> next_knock_over;
	// initialize
	next_knock_over.push({ attack_row, attack_col, board[attack_row][attack_col] - 1 });
	// until everything overthrow
	while (!next_knock_over.empty())
	{
		const statement current = next_knock_over.front();
		next_knock_over.pop();
		for (int i = 1; i <= current.size; i++)
		{
			// next overthrow statement
			const int next_row = current.row + d_row[attack_direction] * i;
			const int next_col = current.col + d_col[attack_direction] * i;
			// condition check
			if (next_row < 0 || next_row >= board_row || next_col < 0 || next_col >= board_col || board_state[next_row][next_col] == 'F')
			{
				continue;
			}
			// next overthrow domino
			next_knock_over.push({ next_row,next_col, board[next_row][next_col] - 1 });
			// overthrow statement
			board_state[next_row][next_col] = 'F';
		}
		// Score increase by the number of dominoes overthrow
		score++;
	}

정답 코드

#include<bits/stdc++.h>
using namespace std;
#define FAST_IO ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr)
// State of overthrow the dominoes
struct statement
{
	int row;
	int col;
	int size;
};
// Direction : E, W, S, N
constexpr int d_row[] = { 0,0,1,-1 };
constexpr int d_col[] = { 1,-1,0,0 };

int select_direction(const int attack_direction)
{
	switch (attack_direction)
	{
	case 'E': return 0;
	case 'W': return 1;
	case 'S': return 2;
	case 'N': return 3;
	default:;
	}
	return -1; // error
}

void overthrow_the_dominoes(const vector<vector<int>>& board, const int board_row, const int board_col,
	vector<vector<char>>& board_state, const int attack_row, const int attack_col,
	const char direction, int& score)
{
	// default value
	board_state[attack_row][attack_col] = 'F';
	const int attack_direction = select_direction(direction);

	// Variable(queue): for storing the next state
	queue<statement> next_knock_over;
	// initialize
	next_knock_over.push({ attack_row, attack_col, board[attack_row][attack_col] - 1 });

	// until everything overthrow
	while (!next_knock_over.empty())
	{
		const statement current = next_knock_over.front();
		next_knock_over.pop();

		for (int i = 1; i <= current.size; i++)
		{
			// next overthrow statement
			const int next_row = current.row + d_row[attack_direction] * i;
			const int next_col = current.col + d_col[attack_direction] * i;

			// condition check
			if (next_row < 0 || next_row >= board_row || next_col < 0 || next_col >= board_col || board_state[next_row][next_col] == 'F')
			{
				continue;
			}

			// next overthrow domino
			next_knock_over.push({ next_row,next_col, board[next_row][next_col] - 1 });
			// overthrow statement
			board_state[next_row][next_col] = 'F';
		}
        
		// Score increase by the number of dominoes overthrow
		score++;
	}
}

void print_board_state(const vector<vector<char>>& board_state)
{
	for (const vector<char>& row : board_state)
	{
		for (const char element : row)
		{
			cout << element << ' ';
		}
		cout << '\n';
	}
}

int main()
{
	FAST_IO;
	// initialize
	int board_row, board_col, game_round;
	cin >> board_row >> board_col >> game_round;
	vector<vector<int>> board(board_row, vector<int>(board_col));
	vector<vector<char>> board_state(board_row, vector<char>(board_col, 'S'));
	// input
	for (vector<int>& row : board)
	{
		for (int& element : row)
		{
			cin >> element;
		}
	}

	int score = 0;
	while (game_round--)
	{
		// attack
		int attack_row, attack_col;
		char attack_direction;
		cin >> attack_row >> attack_col >> attack_direction;
		overthrow_the_dominoes(board, board_row, board_col, board_state, attack_row - 1, attack_col - 1, attack_direction, score);
		// defend
		int defender_row, defender_col;
		cin >> defender_row >> defender_col;
		board_state[defender_row - 1][defender_col - 1] = 'S';
	}
	// print answer
	cout << score << '\n';
	print_board_state(board_state);
	return 0;
}