[백준 23290] 마법사 상어와 복제

++22. 11.04 새로 짠 코드가 더 깔끔한 것 같아서 갱신해본다. 

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

23290번: 마법사 상어와 복제

#include <cstdio>
#include <vector>
#include <cstring>
int M, S;
int sx, sy; // 상어

std::vector<int> V[4 + 2][4 + 2];
std::vector<int> C[4 + 2][4 + 2];	// 복제용
std::vector<int> tmp[4 + 2][4 + 2];	// 물고기 이동용 임시
int smell[4 + 2][4 + 2];

int choice[3 + 2];	// 중복순열 
int visited[4 + 2][4 + 2];	// 상어 방문 
int max_cnt = -1;
int move[3 + 2];	// 상어가 진짜 움직일 방향


void input()
{
	scanf("%d %d", &M, &S);
	for (int i = 0; i < M; i++) {
		int x = 0, y = 0, d = 0;
		scanf("%d %d %d", &x, &y, &d);
		V[x][y].push_back(d);
	}
	scanf("%d %d", &sx, &sy);
}


void cpy_fish()
{
	// 복제마법 시전 
	for (int i = 1; i <= 4; i++) {
		for (int j = 1; j <= 4; j++) {
			if (V[i][j].empty()) continue;
			C[i][j] = V[i][j];
		}
	}
}


void mv_fish()
{
	// 0, 1←, 2↖, 3↑, 4↗, 5→, 6↘, 7↓, 8↙
	int dir_x[9] = { 0, 0, -1, -1, -1, 0, 1, 1, 1 };
	int dir_y[9] = { 0, -1, -1, 0, 1, 1, 1, 0, -1 };

	for (int i = 1; i <= 4; i++) {
		for (int j = 1; j <= 4; j++) {
			if (V[i][j].empty()) continue;
			for (int d : V[i][j]) {
				bool set = false;
				// 반시계 45도 회전하면서 8방향을 탐색해본다 
				for (int p = 0; p < 8; p++) {
					int nd = (d - p < 1) ? d - p + 8 : d - p;
					int nx = i + dir_x[nd];
					int ny = j + dir_y[nd];

					if (nx < 1 || nx > 4 || ny < 1 || ny > 4) continue;
					if (smell[nx][ny]) continue;
					if (nx == sx && ny == sy) continue;
					tmp[nx][ny].push_back(nd);
					set = true;
					break;
				}
				if (set == false) tmp[i][j].push_back(d);
			}
			V[i][j].clear();
		}
	}

	// tmp -> V
	for (int i = 1; i <= 4; i++) {
		for (int j = 1; j <= 4; j++) {
			if (tmp[i][j].empty()) continue;
			V[i][j] = tmp[i][j];
			tmp[i][j].clear();
		}
	}
}


void dfs_init()
{
	memset(choice, 0, sizeof(choice));
	memset(move, 0, sizeof(move));
	max_cnt = -1;
}


int mv_shark()
{
	// 0, 1상 2좌 3하 4우
	int dir_x[5] = { 0, -1, 0, 1, 0 };
	int dir_y[5] = { 0, 0, -1, 0, 1 };
	memset(visited, 0, sizeof(visited));

	int tx = sx; int ty = sy;	// 상어 위치 임시로 받아놓기
	// visited[tx][ty] = 1;		// 상어의 기존 위치는 방문표시 하면 안된다 !!!! 
	int ate = 0;

	for (int i = 1; i <= 3; i++) {
		int nx = tx + dir_x[choice[i]];
		int ny = ty + dir_y[choice[i]];

		if (nx < 1 || nx > 4 || ny < 1 || ny > 4) return -1;
		if (visited[nx][ny] == 0 && !V[nx][ny].empty()) ate += V[nx][ny].size();
		visited[nx][ny] = 1;
		tx = nx, ty = ny;
	}
	return ate;
}



void DFS(int n)
{
	if (n > 3) {
		int cnt = mv_shark();
		if (cnt == -1) return;	// 영역밖을 벗어남
		if (cnt > max_cnt) {
			max_cnt = cnt;
			for (int i = 1; i <= 3; i++) move[i] = choice[i];
		}
		return;
	}

	for (int i = 1; i <= 4; i++) {
		choice[n] = i;
		DFS(n + 1);
	}
}


void real_mv_shark(int time)
{
	// 0, 1상 2좌 3하 4우
	int dir_x[5] = { 0, -1, 0, 1, 0 };
	int dir_y[5] = { 0, 0, -1, 0, 1 };

	for (int i = 1; i <= 3; i++) {
		int nx = sx + dir_x[move[i]];
		int ny = sy + dir_y[move[i]];

		if (!V[nx][ny].empty()) {
			V[nx][ny].clear();
			smell[nx][ny] = time;
		}
		sx = nx, sy = ny;
	}
}




void del_smell(int time)
{
	for (int i = 1; i <= 4; i++) {
		for (int j = 1; j <= 4; j++) {
			if (smell[i][j] == 0) continue;
			// 두 번 전 연습에서 생긴 물고기의 냄새가 사라진다. 
			if (time - 2 == smell[i][j]) smell[i][j] = 0;
		}
	}

}



void cp_done()
{
	// 복제마법 완료 
	for (int i = 1; i <= 4; i++) {
		for (int j = 1; j <= 4; j++) {
			if (C[i][j].empty()) continue;
			for (int d : C[i][j]) {
				V[i][j].push_back(d);
			}
			C[i][j].clear();
		}
	}
}



void simul()
{
	for (int s = 1; s <= S; s++) {
		cpy_fish();
		mv_fish();
		dfs_init();
		DFS(1);
		real_mv_shark(s);
		del_smell(s);
		cp_done();
	}

}


int output()
{
	int remain = 0;
	for (int i = 1; i <= 4; i++) {
		for (int j = 1; j <= 4; j++) {
			remain += V[i][j].size();
		}
	}
	return remain;
}


int main()
{
	input();
	simul();
	printf("%d\n", output());
	return 0;
}

내가 했던 진짜 치명적인 실수 

1. 상어의 기존 위치를 방문처리 해줬는데, 이렇게 하면 안된다. 상어의 현재 위치는 상어의 이동경로에 포함될 수도, 안될 수도 있다. 현재칸을 포함하지 않고 3번 움직이는 것이다. 

2. (이건 금방 디버깅하긴 했지만..) 상어가 물고기를 아예 못잡아먹을 수도 있다. 이러한 경우 "잡아먹은 물고기의 최대 마리 수"는 0이다. 따라서 max_cnt의 초기값을 0으로 잡으면 상어의 이동경로가 제대로 갱신이 되지 않는다. 

따라서 -1 로 잡아주어야 한다 .

---

물고기의 정보를 구조체로 관리하면서 풀었던 이전 코드.. 

맵의 사이즈가 작고, 물고기 하나하나의 정보가 중요한 것이 아니므로(예컨대 물고기 별로 번호가 부여되어 있어서 냄새를 구분해야 한다든지..) 아래와 같이 푸는 것은 다소 비효율 적일 수 있다. 

#include <cstdio>
#include <vector>
#include <algorithm>
int M, S;		// 물고기수, 연습횟수
int sx, sy;		// 초기 상어 위치
int tx, ty;		// DFS 돌면서 갱신되는 상어 위치 

struct _ft
{
	int x, y;
	int dir;
	bool alive = true;	// 초기값 true
};

_ft Fish[1000000 + 2];
_ft Tmp[1000000 + 2];

std::vector<int> C[4 + 2][4 + 2];	// 원본맵 
int Smell[4 + 2][4 + 2];			// 물고기는 죽으면 냄새를 남긴다
int cnt;
int choice[3 + 2];	// 상 좌 하 우 => 3개 선택
int real_choice[3 + 2];
int visited[4 + 2][4 + 2];	// 상어 물고기 한 번 잡아먹은 곳은 다시 안잡아먹도록  

// 1상 2좌 3하 4우
int dir_sx[5] = { 0, -1, 0, 1, 0 };
int dir_sy[5] = { 0, 0, -1, 0, 1 };


void input()
{
	scanf("%d %d", &M, &S);
	for (int i = 1; i <= M; i++) {
		scanf("%d %d %d", &Fish[i].x, &Fish[i].y, &Fish[i].dir);
	}
	scanf("%d %d", &sx, &sy);
}



void copy_fish()
{
	for (int i = 1; i <= M; i++) {
		Tmp[i] = Fish[i];
	}
}


void move_fish()
{
	for (int i = 1; i <= 4; i++) {
		for (int j = 1; j <= 4; j++) {
			C[i][j].clear();
		}
	}

	// 0 1←, 2↖, 3↑, 4↗, 5→, 6↘, 7↓, 8↙ 
	static int dir_x[9] = { 0, 0, -1, -1, -1, 0, 1, 1, 1 };
	static int dir_y[9] = { 0, -1, -1, 0, 1, 1, 1, 0, -1 };

	// 물고기가 이동할 수 있는 칸 탐색 
	//debug_f();
	for (int i = 1; i <= M; i++) {
		int x = Fish[i].x;
		int y = Fish[i].y;
		int dir = Fish[i].dir;
		for (int p = 0; p < 8; p++) {
			//printf("%d", p);
			if (dir == 0) dir = 8;
			int nx = x + dir_x[dir];
			int ny = y + dir_y[dir];
			if (nx < 1 || nx > 4 || ny < 1 || ny > 4) {
				dir--;
				continue;	// 영역밖 스루
			}
			if (nx == sx && ny == sy) {
				dir--;
				continue;	// 상어있는 곳 스루
			}
			if (Smell[nx][ny]) {
				dir--;
				continue;		// 물고기 냄새 있으면 스루
			}
			Fish[i].x = nx;
			Fish[i].y = ny;
			Fish[i].dir = dir;
			break;
		}
	}
	// 진짜 이동 
	for (int i = 1; i <= M; i++) {
		int x = Fish[i].x;
		int y = Fish[i].y;
		C[x][y].push_back(i);
	}
	//debug_f();
}



int move_shark()
{
	std::fill(&visited[0][0], &visited[0][0] + sizeof(visited) / sizeof(int), 0);

	int dead = 0;
	tx = sx, ty = sy;

	int nx = 0, ny = 0;
	for (int i = 1; i <= 3; i++) {
		nx = tx + dir_sx[choice[i]];
		ny = ty + dir_sy[choice[i]];

		if (nx < 1 || nx > 4 || ny < 1 || ny > 4) return -1;	// 이동하는 칸 중에 격자의 범위를 벗어나는 칸이 있으면 
															// 그 방법은 불가능한 이동방법이다. 
		if (visited[nx][ny]) continue;
		if (!C[nx][ny].empty()) dead += C[nx][ny].size();
		visited[nx][ny] = 1;
		tx = nx, ty = ny;
	}
	return dead;
}



void Rep_Permu(int n)
{
	if (n > 3) {
		int tmp = move_shark();
		if (cnt < tmp) {	// 사전순으로 가장 앞서는 방법 채택
			cnt = tmp;
			for (int i = 1; i <= 3; i++) {
				real_choice[i] = choice[i];
			}
		}
		return;
	}

	for (int i = 1; i <= 4; i++) {
		choice[n] = i;
		Rep_Permu(n + 1);
	}
}


void real_move_shark(int s)
{
	int nx = 0, ny = 0;
	for (int i = 1; i <= 3; i++) {
		nx = sx + dir_sx[real_choice[i]];
		ny = sy + dir_sy[real_choice[i]];

		if (nx < 1 || nx > 4 || ny < 1 || ny > 4) continue;
		if (!C[nx][ny].empty()) {
			for (int k = 0; k < C[nx][ny].size(); k++) {
				Fish[C[nx][ny][k]].alive = false;
				Smell[nx][ny] = s;	// s회에 남긴 냄새
			}
			C[nx][ny].clear();
		}
		sx = nx, sy = ny;
	}
}



void del_smell(int s)
{
	for (int i = 1; i <= 4; i++) {
		for (int j = 1; j <= 4; j++) {
			if (Smell[i][j] == 0) continue;
			if (Smell[i][j] == s - 2) Smell[i][j] = 0;	// 두번 전 연습에서 생긴 물고기의 냄새가 격자에서 사라진다. 
		}
	}
}


void copy_done()
{
	for (int i = 1; i <= M; i++) {	// 1에서 사용한 복제 마법이 완료된다. 
		int x = Tmp[i].x;
		int y = Tmp[i].y;
		C[x][y].push_back(i);
	}

	int num = M + 1;
	for (int i = 1; i <= M; i++) {
		if (Fish[i].alive == false) continue;
		if (Fish[i].dir == 0) break;

		Tmp[num] = Fish[i];
		num++;
	}
	for (int i = 1; i <= M; i++) {
		Fish[i] = { 0, 0, 0, true };
	}
	M = num - 1;
	for (int i = 1; i <= M; i++) {
		Fish[i] = Tmp[i];
	}
	for (int i = 1; i <= M; i++) {
		Tmp[i] = { 0, 0, 0, true };
	}
}



void simul()
{
	for (int i = 1; i <= S; i++) {
		copy_fish();
		move_fish();
		cnt = -1;
		Rep_Permu(1);
		real_move_shark(i);
		del_smell(i);
		copy_done();
	}
}



int output()
{
	int cnt = 0;
	for (int i = 1; i <= M; i++) {
		if (Fish[i].alive == true) cnt++;
	}
	return cnt;
}


int main()
{
	input();
	simul();
	int ans = output();
	printf("%d\n", ans);
	return 0;
}