[BOJ][백준]Simulation-17135번 캐슬 디팬스

https://www.acmicpc.net/problem/17135

17135번: 캐슬 디펜스

문제

캐슬 디펜스는 성을 향해 몰려오는 적을 잡는 턴 방식의 게임이다. 게임이 진행되는 곳은 크기가 N×M인 격자판으로 나타낼 수 있다. 격자판은 1×1 크기의 칸으로 나누어져 있고, 각 칸에 포함된 적의 수는 최대 하나이다. 격자판의 N번행의 바로 아래(N+1번 행)의 모든 칸에는 성이 있다.

성을 적에게서 지키기 위해 궁수 3명을 배치하려고 한다. 궁수는 성이 있는 칸에 배치할 수 있고, 하나의 칸에는 최대 1명의 궁수만 있을 수 있다. 각각의 턴마다 궁수는 적 하나를 공격할 수 있고, 모든 궁수는 동시에 공격한다. 궁수가 공격하는 적은 거리가 D이하인 적 중에서 가장 가까운 적이고, 그러한 적이 여럿일 경우에는 가장 왼쪽에 있는 적을 공격한다. 같은 적이 여러 궁수에게 공격당할 수 있다. 공격받은 적은 게임에서 제외된다. 궁수의 공격이 끝나면, 적이 이동한다. 적은 아래로 한 칸 이동하며, 성이 있는 칸으로 이동한 경우에는 게임에서 제외된다. 모든 적이 격자판에서 제외되면 게임이 끝난다. 

게임 설명에서 보다시피 궁수를 배치한 이후의 게임 진행은 정해져있다. 따라서, 이 게임은 궁수의 위치가 중요하다. 격자판의 상태가 주어졌을 때, 궁수의 공격으로 제거할 수 있는 적의 최대 수를 계산해보자.

격자판의 두 위치 (r1, c1), (r2, c2)의 거리는 |r1-r2| + |c1-c2|이다.

입력

첫째 줄에 격자판 행의 수 N, 열의 수 M, 궁수의 공격 거리 제한 D가 주어진다. 둘째 줄부터 N개의 줄에는 격자판의 상태가 주어진다. 0은 빈 칸, 1은 적이 있는 칸이다.

출력

첫째 줄에 궁수의 공격으로 제거할 수 있는 적의 최대 수를 출력한다.

제한

• 3 ≤ N, M ≤ 15
• 1 ≤ D ≤ 10

****************************************************************************************************

 

요즘 채점현황을 보면 절반이 삼성역테,코테 문제들이다.

인구이동,나무재테크,로봇청소기,테트로미노... 이러한 문제들을 별로 좋아하진 않는데,

(구현하기에 시간이 너무 많이소요되고,,, 복잡하기도 하고,,)

어쨌든 삼성기출이니 풀어봤다.

약간의 테크닉만 가지고있다면 그냥 문제에서 하라는대로 구현하면 되는문제다.

그게 너무나도 많아서 문제지만..

먼저 내가 이문제에서 사용한 테크닉은,

1.bfs(궁수로부터 거리측정)

2.순열(궁수3명 배치)

3.궁수가 동시에 적을 겨냥했을때, 적을 두번죽일 순 없으니, 중복제거

4.bool 함수를 이용한 sort 함수의 vector 정렬

..나열하고보니 까다로운 문제이긴 했던것 같다. 코드보면서 얘기를 해보자면,

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
const int MAX_N = 15 + 2;
int N, M, D, maxSum = 0;
int board[MAX_N][MAX_N];
int board_cpy[MAX_N][MAX_N];
vector <pair<int, int>> archer;
int goY[4] = { 0,0,1,-1 };
int goX[4] = { 1,-1,0,0 };

bool Vcompare(pair<pair <int,int>,int> &a, pair<pair<int, int>,int> &b)
{
	if (a.second != b.second)
		return a.second < b.second;
	else
		return a.first.second < b.first.second;
}

bool is_in_board(int y, int x)
{
	if (y<1 || y>N || x<1 || x>M)
		return false;
	return true;
}

void board_print()
{
	for (int i = 1; i <= N; i++)
	{
		for (int j = 1; j <= M; j++)
			cout << board[i][j];
		cout << endl;
	}
	cout << endl;
}

void board_recover()
{
	for (int i = 1; i <= N; i++)
		for (int j = 1; j <= M; j++)
			board[i][j] = board_cpy[i][j];
}

void board_move()
{
	int tmp_board[MAX_N][MAX_N];
	for (int i = 1; i <= N; i++)
	{
		if (i == 1)
			for (int j = 1; j <= M; j++)
				tmp_board[i][j] = 0;
		else
			for (int j = 1; j <= M; j++)
				tmp_board[i][j] = board[i - 1][j];
	}
	
	for (int i = 1; i <= N; i++)
		for (int j = 1; j <= M; j++)
			board[i][j] = tmp_board[i][j];
}

void board_remove( vector <pair<int,int>> &deleted)
{
	for (auto i : deleted)
		board[i.first][i.second] = 0;
	
}

int bfs()
{
	vector <pair<int, int>> deleted;
	for (int i = 0; i < 3; i++)
	{
		int archerY = archer[i].first, archerX = archer[i].second;
		vector <pair < pair<int,int> ,int> > can_delete; //y좌표,x좌표,거리
		int visited[MAX_N][MAX_N] = { 0, };
		queue <pair<int, int>> q;
		visited[archerY][archerX] = 1;
		q.push(make_pair(archerY, archerX));
		while (!q.empty())
		{
			int nowY = q.front().first;
			int nowX = q.front().second;
			q.pop();
			if (board[nowY][nowX] == 1 && visited[nowY][nowX] - 1 <= D)
			{
				can_delete.push_back(make_pair(make_pair(nowY, nowX), visited[nowY][nowX] - 1));
				continue;
			}
			if (visited[nowY][nowX] - 1 > D)
				continue;
			for (int j = 0; j < 4; j++)
			{
				int nextY = nowY + goY[j], nextX = nowX + goX[j];
				if (!visited[nextY][nextX] && is_in_board(nextY, nextX))
				{
					visited[nextY][nextX] = visited[nowY][nowX] + 1;
					q.push(make_pair(nextY, nextX));
				}
			}
		}
		if (can_delete.size() > 0)
		{
        	//1.거리가짧은순으로 2.거리가 같으면 x좌표가 낮은순으로
			sort(can_delete.begin(), can_delete.end(), Vcompare); 
			deleted.push_back(can_delete[0].first);
		}
	}
    //deleted에 중복제거(똑같은게 있으면 return deleted.size()에서 오류가 날것)
	deleted.erase(unique(deleted.begin(), deleted.end()), deleted.end());
	board_remove(deleted);
	return deleted.size();
}

void archer_place(int x, int n)
{
	if (n == 3)
	{
		int sum = 0, time = N + 1;
		while (time--)
		{
			sum += bfs();
			board_move();
		}
		maxSum = max(sum, maxSum);
		board_recover();
		return;
	}

		for (int j = x; j <= M; j++)
		{
			bool overlap = false;
			for (int k = 0; k < n; k++)
				if (archer[k] == make_pair(N+1, j))
					overlap = true;
			if (!overlap)
			{
				archer[n] = make_pair(N+1, j);
				archer_place( j, n + 1);
				archer[n] = make_pair(0, 0);
			}
		}
	
}

int main()
{
	cin >> N >> M >> D;
	for (int i = 1; i <= N; i++)
		for (int j = 1; j <= M; j++)
		{
			cin >> board[i][j];
			board_cpy[i][j] = board[i][j];
		}
	archer.resize(3);
	archer_place(1, 0);
	cout << maxSum;
}

.

아, 정말 너무나 길다.

함수 선언하지 않고 main함수에 다 때려박았으면 혼종도 그런 혼종이 없을 뻔 했다.

위에서부터 찬찬히 살펴보자면, pair vector 로 궁수들의 위치를 담아놓는 벡터와,

Vcompare함수가 있는데, compare함수를 이용한 sort정렬을 사용하는방법은 나중에 포스팅해서

링크 올릴려고한다. 뭔가 되게 까다로울 것 같지만 그렇지 않다.

그 밑으로는 여러 board_recover, board_move함수가 있는데 이건 읽으면 바로 이해가 가능할 수 있으니

생략을하고, 더 밑으로내려오면 bfs함수가 있다. 정말 어지럽게 선언하고 구현했는데,

어떻게 하면 더 깔끔하게 구현할수 있을까 고민을하다. 주석을 달았는데 보기 편하실지 모르겠습니다..

각각의 궁수마다 bfs를 돌려서, can_delete에 죽일수있는 적의 좌표와,거리를 담아 정렬을한후,

deleted, 즉 죽이기가 확정된 단 한명의 적만 넣는다. 이방식을 3명의 궁수가 하고,

그렇다면 deleted 벡터에는 최소0명,최대 3명의 적이 들어가게되는데, 여기서 또 처리를 해야할 점은,

return deleted.size()함수의 변수인데, 만약 A,B궁수가 둘다 E란 적을 죽이고 deleted벡터에 넣는다면

우리가 리턴해야할 사이즈는 2가 아닌 1이되어야 합니다. 이 말이 이해가안되면 다시 문제를 찬찬히 읽기를 바랍니다.

궁수는 같은 적을 겨냥할수있기 때문에(궁수가 활사위를 당기는 행위가 동시다발적이기 때문에)

이같은 버그를 유발하기 쉬운 사례가 생기게됩니다. 그렇기때문에 deleted.erase()함수를 이용해 중복을 

제거해준뒤, 드디어 함수를 끝내게 됩니다. 그다음은 archer_place()함수인데, 특이할점 없는

전형적인 브루트 포스형 함수입니다. 조금 독특한점이라면 time변수는 N+1만큼 선언이 되어있는데,

(y줄이 한번씩 이동+처음의 맵) 이라고 설명을하면 조금 이해가 가시려나요? 그렇게 맵이 한줄씩 이동을

하고 다 탐색을하면 maxSum을 갱신해준후, 한바탕 전쟁이 치뤄진 board를 recover해준후 이번 궁수배치

시뮬레이션은 종료를하게됩니다.

아,정말 말이길어졌는데 그만큼 빡셌던 문제입니다. 맞추시더라도 코드리뷰 확실히 하셔야 할것 같습니다.

좋게말하면 어렵고 코드구현력을 많이보는 문제지만 안좋게 말하면 좀 더러운 문제네요..😡

(사실 저는 궁수를 성벽이아닌 N*M배열에 배치해야하는 줄 알고 삽질을 1시간 넘게해서 그럽니다.)

리뷰해야할 문제가 많은데, 앞으로는 꾸준히 올리도록 해야겠네요..🙋