[백준] 17135번: 캐슬 디펜스

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

17135번: 캐슬 디펜스

 

문제 이해

0부터 M-1까지의 위치 중에 세 자리를 고른다. (궁수 위치 선정) DFS를 이용했다. (삼중 for문 이용해도 ok)

3자리 다 정했으면 시뮬레이션을 돌려본다.

 

Simulation()

근데 이 시뮬레이션이 오히려 복잡했다. 

궁수 세 명 각각 BFS를 돌려서 가장 거리가 짧은 적 중에, 가장 왼쪽에 있는 적을 죽여야 한다. 근데 다른 궁수들이 같은 적을 죽일 수 있어서 바로 죽이면 안되고, 셋 모두 타겟을 정한 후에 죽여줘야 한다. 그래서 각 궁수별로 죽일 적의 좌표를 selpos라는 배열에 저장해두었다.

만약 D거리 이내에 죽일 적이 없으면 selpos에는 INF 값이 들어있어서 패스하면 된다.

 

< 주의할 점 >

나는 단계별로 궁수를 위로 전진시키는 방식으로 적이 캐슬 안으로 들어오는 것을 대체했다.

근데 이때 발생한 문제가, 이렇게 궁수의 y좌표를 위로 당기게 되면, y행에 적이 남아있어서 BFS에서 궁수 위치로부터 좌, 우로 움직였을 때 문제에 따르면 이미 캐슬 안으로 들어온 적을 타겟으로 삼을 수 있다는 점이다.

따라서 궁수의 y좌표를 위로 당기는 동시에, 그 행에 적들을 다 없애준 상태에서 BFS를 돌려야 한다. 

 

이 궁수들의 위치에서 Simulation이 완료되었다면 맵을 원상복귀 시키는 것도 잊지 말자

int Simulation(void) {
	memcpy(tmpmap, map, sizeof(map));
	int cnt = 0; 
	for (int r = N; r >= 0; ) {
		memset(selpos, 0, sizeof(selpos));
		for(int i = 0; i<3; i++){ // 죽이기
			BFS(i, r, sel[i]);
		}
		for (int i = 0; i < 3; i++) {
			if (selpos[i].y == INF) continue;
			if (map[selpos[i].y][selpos[i].x] != 0) {
				map[selpos[i].y][selpos[i].x] = 0;
				cnt++;
			}
		}
		r--;
		for (int i = 0; i < M; i++) map[r][i] = 0;
		if (Check(r)) break;
	}
	memcpy(map, tmpmap, sizeof(tmpmap)); // 원상복귀
	return cnt;
}

 

BFS()

BFS는 좌, 상, 우를 탐색하며 나아간다. 같은 거리에 있는 적이 여러 명일 수 있어서 최소거리(min), 타겟의 좌표(sel[no])를 모두 최댓값으로 맞추고 시작했다. 

그래서 최소거리에 있는 타겟보다 지금 찾은 타겟의 거리가 짧으면 최소거리, 타겟의 좌표를 모두 업데이트 해줬다.

만약 거리가 같아면 x좌표를 비교해서 지금 찾은 타겟의 x좌표가 더 작으면 업데이트 해줬다.

이때 거리가 D이상이 되거나, 찾은 최소거리(min)보다 거리가 늘어나게 되면 continue할 수 있도록 가지를 쳐줬다.

int BFS(int no, int y, int x) {
	int min = INF;
	selpos[no].y = INF, selpos[no].x = INF;
	wp = rp = 0;
	memset(visited, 0, sizeof(visited));

	enq(y, x, 0);
	visited[y][x] = 1;
	while (!empty()) {
		ELE cur = deq();
		if (cur.t >= D || cur.t >= min) continue;
		for (int i = 0; i < 3; i++) {
			int nx = cur.x + dx[i];
			int ny = cur.y + dy[i];
			if (ny < 0 || ny >= N || nx < 0 || nx >= M) continue;
			if (visited[ny][nx] == 1) continue;
			if (map[ny][nx] == 1) {
				if(selpos[no].x > nx){
					selpos[no].y = ny, selpos[no].x = nx;
					min = cur.t+1; 
				}
				continue;
			}
			enq(ny, nx, cur.t + 1);
			visited[ny][nx];
		}
	}
	return 0;
}

 

전체 코드

#include <stdio.h>
#include <string.h>
#define MAXNM 15
#define INF 0x7fffffff

int N, M, D;
int map[MAXNM + 5][MAXNM + 5];
int tmpmap[MAXNM + 5][MAXNM + 5];
int visited[MAXNM + 5][MAXNM + 5];
int enemy;
int sel[3 + 2];
int max;

void Get_Input(void) {
	scanf("%d %d %d", &N, &M, &D);
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			scanf("%d", &map[i][j]);
		}
	}
}

typedef struct st {
	int y, x, t;
}ELE;
ELE q[MAXNM * MAXNM * 10];
int wp, rp;
void enq(int y, int x, int t) { q[wp].y = y, q[wp].x = x, q[wp++].t = t; }
ELE deq(void) { return q[rp++]; }
int empty(void) { return wp == rp; }

ELE selpos[3 + 2];

int dy[] = { 0, -1, 0 };
int dx[] = { -1, 0, 1 };

int BFS(int no, int y, int x) {
	int min = INF;
	selpos[no].y = INF, selpos[no].x = INF;
	wp = rp = 0;
	memset(visited, 0, sizeof(visited));

	enq(y, x, 0);
	visited[y][x] = 1;
	while (!empty()) {
		ELE cur = deq();
		if (cur.t >= D || cur.t >= min) continue;
		for (int i = 0; i < 3; i++) {
			int nx = cur.x + dx[i];
			int ny = cur.y + dy[i];
			if (ny < 0 || ny >= N || nx < 0 || nx >= M) continue;
			if (visited[ny][nx] == 1) continue;
			if (map[ny][nx] == 1) {
				if(selpos[no].x > nx){
					selpos[no].y = ny, selpos[no].x = nx;
					min = cur.t+1; 
				}
				continue;
			}
			enq(ny, nx, cur.t + 1);
			visited[ny][nx];
		}
	}
	return 0;
}

int Check(int r) {
	for (int i = 0; i < r; i++) {
		for (int j = 0; j < M; j++) {
			if (map[i][j] == 1) return 0;
		}
	}
	return 1;
}

int Simulation(void) {
	memcpy(tmpmap, map, sizeof(map));
	int cnt = 0; 
	for (int r = N; r >= 0; ) {
		memset(selpos, 0, sizeof(selpos));
		for(int i = 0; i<3; i++){ // 죽이기
			BFS(i, r, sel[i]);
		}
		for (int i = 0; i < 3; i++) {
			if (selpos[i].y == INF) continue;
			if (map[selpos[i].y][selpos[i].x] != 0) {
				map[selpos[i].y][selpos[i].x] = 0;
				cnt++;
			}
		}
		r--;
		for (int i = 0; i < M; i++) map[r][i] = 0;
		if (Check(r)) break;
	}
	memcpy(map, tmpmap, sizeof(tmpmap)); // 원상복귀
	return cnt;
}

void DFS(int idx, int cnt) {
	// 종료
	if (cnt == 3) {
		int res = Simulation();
		if (res > max) max = res;
		return;
	}
	// 재귀
	for (int i = idx; i < M; i++) {
		sel[cnt] = i;
		DFS(i + 1, cnt + 1);
	}
}

int main(void) {
	Get_Input();
	DFS(0, 0);
	printf("%d", max);
	return 0;
}