백준 - 마법사 상어와 복제 (23290)

1. 문제 링크

문제 링크

2. 풀이

1. 맵 설계

vector<int> fishs[4][4], prepare[4][4];

2차원 백터 배열로 설계했습니다.
백터 안에는 물고기가 가지는 방향이 들어갑니다.
fishs는 물고기와 상어의 이동을 시뮬레이션 하는 맵이고
prepare는 물고기 복제 버그를 준비하는 맵입니다.

2. 상어의 모든 이동 경로를 오름차순으로 만들어놓기

vector<vector<int>> sharkPaths;

for (int i = 0; i < 4; i++)
	for (int j = 0; j < 4; j++)
		for (int k = 0; k < 4; k++)
			sharkPaths.push_back({ i, j, k });

상어의 이동 경로는 끽해야 64개 밖에 안됩니다.
3중 포문으로 sharkPaths에 모든 경로를 저장합니다.

3. 복사 버그 마법 준비하기

void copyBoard(vector<int> from[][4], vector<int> to[][4]) {
	for (int i = 0; i < 4; i++)
		for (int j = 0; j < 4; j++)
			to[i][j] = from[i][j];
} 

copyBoard(fishs, prepare);

별 거 없습니다.
fishs의 현재 상황을 prepare로 복사합니다.

4. 물고기 움직이기

void moveFishs() {
	vector<int> tmp[4][4];

	for (int i = 0; i < 4; i++) {
		for (int j = 0; j < 4; j++) {
			for (int d : fishs[i][j]) {
				int isMove = 0;

				// 8방향 시도
				for (int dir = 0; dir < 8; dir++) {
					int y = i + fy[d];
					int x = j + fx[d];

					// 나가지 않았고 물고기 냄새가 없고 상어도 없을 때
					if (!isOut(y, x) && smell[y][x] == 0 && (y != shy || x != shx)) {
						tmp[y][x].push_back(d);
						isMove = 1;
						break;
					}

					d = (d + 7) % 8;
				}

				// 못 움직였을 땐 현재 자리에 현재 방향으로 넣기
				if (!isMove) tmp[i][j].push_back(d);
			}
		}
	}

	copyBoard(tmp, fishs);
}

tmp맵을 만들어서 물고기 움직임을 기록하고
tmp맵을 fishs맵으로 복사합니다.

5. 물고기 냄새 감소시키기

void decreaseSmell() {
	for (int i = 0; i < 4; i++)
		for (int j = 0; j < 4; j++)
			smell[i][j] = max(0, smell[i][j] - 1);
}

전구간을 돌면서 1씩 감소시킵니다.

6. 상어 움직이기

void moveShark() {
	int maxFishHuntCnt = -1;
	int pathNum = -1;

	for (int i = 0; i < 64; i++) {
		int fishHuntCnt = 0;
		int ny = shy;
		int nx = shx;
		int isWay = 1;

		for (int d : sharkPaths[i]) {
			ny += sy[d];
			nx += sx[d];

			// 맵을 벗어날 때
			if (isOut(ny, nx)) {
				isWay = 0;
				break;
			}

			// 먹지 않았던 물고기일 때
			if (!eated[ny][nx]) {
				fishHuntCnt += fishs[ny][nx].size();
				eated[ny][nx] = 1; // 먹었다 표시
			}
		}

		ny = shy;
		nx = shx;

		// eated 배열 초기화
		for (int d : sharkPaths[i]) {
			ny += sy[d];
			nx += sx[d];

			if (!isOut(ny, nx)) eated[ny][nx] = 0;
		}

		// 갈 수 있는 길이고 물고기를 더 많이 먹었을 때
		if (isWay && fishHuntCnt > maxFishHuntCnt) {
			maxFishHuntCnt = fishHuntCnt;
			pathNum = i;
		}
	}

	// 상어 이동
	for (int d : sharkPaths[pathNum]) {
		shy += sy[d];
		shx += sx[d];

		if (fishs[shy][shx].size() > 0) {
			smell[shy][shx] = 2; // 물고기 냄새를 2로 설정
			fishs[shy][shx].clear();
		}
	}
}

2번에서 만든 상어의 모든 이동 경로를 다 따져봐서
제일 물고기를 많이 사냥할 수 있는 경로로 상어를 이동시킵니다.
이 때 물고기를 사냥할 때 물고기 냄새를 2로 설정합니다.
그리고 단계마다 냄새를 1씩 감소시키면
전전단계의 물고기의 냄새를 제거할 수 있습니다.

7. 물복사 버그 마법 시전

void copyBug() {
	for (int i = 0; i < 4; i++) {
		for (int j = 0; j < 4; j++) {
			for (int d : prepare[i][j]) {
				fishs[i][j].push_back(d);
			}
		}
	}
}

3번에서 prepare맵에 복사해놨던 물고기들을
fishs에 옮겨줍니다.

3. 전체 코드

#include <bits/stdc++.h>

using namespace std;

int m, s, shy, shx;
int fy[8] = { 0, -1, -1, -1, 0, 1, 1, 1 };
int fx[8] = { -1, -1, 0, 1, 1, 1, 0, -1 };
int sy[4] = { -1, 0, 1, 0 };
int sx[4] = { 0, -1, 0, 1 };
int smell[4][4], eated[4][4];
vector<vector<int>> sharkPaths;
vector<int> fishs[4][4], prepare[4][4];

bool isOut(int y, int x) {
	return y < 0 || y >= 4 || x < 0 || x >= 4;
}

void copyBoard(vector<int> from[][4], vector<int> to[][4]) {
	for (int i = 0; i < 4; i++)
		for (int j = 0; j < 4; j++)
			to[i][j] = from[i][j];
}

void moveFishs() {
	vector<int> tmp[4][4];

	for (int i = 0; i < 4; i++) {
		for (int j = 0; j < 4; j++) {
			for (int d : fishs[i][j]) {
				int isMove = 0;

				// 8방향 시도
				for (int dir = 0; dir < 8; dir++) {
					int y = i + fy[d];
					int x = j + fx[d];

					// 나가지 않았고 물고기 냄새가 없고 상어도 없을 때
					if (!isOut(y, x) && smell[y][x] == 0 && (y != shy || x != shx)) {
						tmp[y][x].push_back(d);
						isMove = 1;
						break;
					}

					d = (d + 7) % 8;
				}

				// 못 움직였을 땐 현재 자리에 현재 방향으로 넣기
				if (!isMove) tmp[i][j].push_back(d);
			}
		}
	}

	copyBoard(tmp, fishs);
}

void decreaseSmell() {
	for (int i = 0; i < 4; i++)
		for (int j = 0; j < 4; j++)
			smell[i][j] = max(0, smell[i][j] - 1);
}

void moveShark() {
	int maxFishHuntCnt = -1;
	int pathNum = -1;

	for (int i = 0; i < 64; i++) {
		int fishHuntCnt = 0;
		int ny = shy;
		int nx = shx;
		int isWay = 1;

		for (int d : sharkPaths[i]) {
			ny += sy[d];
			nx += sx[d];

			// 맵을 벗어날 때
			if (isOut(ny, nx)) {
				isWay = 0;
				break;
			}

			// 먹지 않았던 물고기일 때
			if (!eated[ny][nx]) {
				fishHuntCnt += fishs[ny][nx].size();
				eated[ny][nx] = 1; // 먹었다 표시
			}
		}

		ny = shy;
		nx = shx;

		// eated 배열 초기화
		for (int d : sharkPaths[i]) {
			ny += sy[d];
			nx += sx[d];

			if (!isOut(ny, nx)) eated[ny][nx] = 0;
		}

		// 갈 수 있는 길이고 물고기를 더 많이 먹었을 때
		if (isWay && fishHuntCnt > maxFishHuntCnt) {
			maxFishHuntCnt = fishHuntCnt;
			pathNum = i;
		}
	}

	// 상어 이동
	for (int d : sharkPaths[pathNum]) {
		shy += sy[d];
		shx += sx[d];

		if (fishs[shy][shx].size() > 0) {
			smell[shy][shx] = 2;
			fishs[shy][shx].clear();
		}
	}
}

void copyBug() {
	for (int i = 0; i < 4; i++) {
		for (int j = 0; j < 4; j++) {
			for (int d : prepare[i][j]) {
				fishs[i][j].push_back(d);
			}
		}
	}
}

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

	cin >> m >> s;

	for (int i = 0; i < m; i++) {
		int y, x, d;
		cin >> y >> x >> d;
		fishs[y - 1][x - 1].push_back(d - 1);
	}

	cin >> shy >> shx;
	shy--;
	shx--;

	for (int i = 0; i < 4; i++)
		for (int j = 0; j < 4; j++)
			for (int k = 0; k < 4; k++)
				sharkPaths.push_back({ i, j, k });

	while (s--) {
		copyBoard(fishs, prepare);
		moveFishs();
		decreaseSmell();
		moveShark();
		copyBug();
	}

	int ans = 0;

	for (int i = 0; i < 4; i++)
		for (int j = 0; j < 4; j++)
			ans += fishs[i][j].size();

	cout << ans;

	return 0;
}