[백준]19236_청소년 상어

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

Solved

✔ 알고리즘 분류: 구현, 백트래킹, 시뮬레이션
✔ 움직일 수 있는 방향은 상하좌우+대각선
✔ 물고기들이 작은 번호부터 순서대로 한 칸씩 이동 후 상어가 이동한다. 각 물고기는 방향이 이동할 수 있는 칸을 향할 때까지 방향을 45도 반시계 회전시킨다.
✔ 상어는 방향에 있는 칸으로 이동할 수 있는데 한 번에 여러 개의 칸을 이동할 수 있고 이동하는 중 지나가는 칸에 있는 물고기는 먹지 않는다. 물고기가 없는 칸으로는 이동할 수 없다. 상어가 이동한 후 물고기가 다시 이동한다.
✔ 상어가 이동할 수 있는 칸이 없으면 공간에서 벗어나 집으로 간다.
✔ 상어가 먹을 수 있는 물고기 번호의 합의 최댓값을 구해보자
✔ 너무나 정직한 구현+백트래킹 문제다. 보드의 크기도 4*4이니 백트래킹 깊이가 깊어도 할만하다.
✔ 데이터 세팅:
2차원 배열 board엔 shark, 물고기 번호, 죽은 물고기 번호가 있다.
2차원 배열 fish[i][0]에는 i번 물고기의 위치 정보, fish[i][1]엔 i번 물고기의 방향이 있다.
이는 물고기와 상어의 빠른 이동을 위해 필요하다. 물고기는 보드판의 row와 column 순이 아닌 각자의 번호 순대로 이동하고 상어는 백트래킹 할 때 빠른 정보의 업데이트를 위해 필요하다.

using namespace std;
#include <iostream>
#include <tuple>
#include <cstring>

// 북부터 시계방향으로 1,2,3,4 ,,,
int board[4][4]; // 1~16: 물고기, 0: shark, -1:죽은 물고기
int fish[17][2]; //위치, 방향
int answer = -1;


pair<int, int> direction(int x, int y, int d) {
	switch (d) {
	case 1: x -= 1;
		break;
	case 2: x -= 1; y -= 1;
		break;
	case 3: y -= 1;
		break;
	case 4: x += 1; y -= 1;
		break;
	case 5: x += 1;
		break;
	case 6: x += 1; y += 1;
		break;
	case 7: y += 1;
		break;
	case 8: x -= 1; y += 1;
		break;
	}
	return make_pair(x, y);
}

bool inRange(int x, int y) {
	return 0 <= x && x < 4 && 0 <= y && y < 4;
}

void moveFish() {
	for (int i = 1; i <= 16; i++) {
		if (fish[i][0] == -1) continue; //죽은 물고기
		int x=fish[i][0]/4, y=fish[i][0]%4, nx=x, ny=y;
		int cnt = 0;
		while (1) {
			tie(nx, ny) = direction(x, y, fish[i][1]);
			if (!inRange(nx, ny) || board[nx][ny]==0) {
				if (++cnt == 8) break;
				fish[i][1]++;
				if (fish[i][1] == 9) fish[i][1] = 1;
			}
			else {
				if (board[nx][ny] != -1)
					swap(fish[board[x][y]][0], fish[board[nx][ny]][0]);
				else
					fish[board[x][y]][0] = nx * 4 + ny;
				swap(board[x][y], board[nx][ny]);
				break;
			}
		}
	}
}
void solve(int x, int y, int d, int sum) {
	int dup[4][4];
	int fdup[17][2];
	int nx = x, ny = y;

	for (int i = 1; i <= 16; i++) {
		fdup[i][0] = fish[i][0];
		fdup[i][1] = fish[i][1];
	}
	memcpy(dup, board, sizeof(dup));

	moveFish();
	while (1) {
		tie(nx, ny) = direction(nx, ny, d);
		if (inRange(nx, ny)) {
			//shark moves and eat
			int idx = board[nx][ny];
			if (idx == -1) continue; //물고기 없음
			board[x][y] = -1;
			board[nx][ny] = 0;
			fish[idx][0] = -1;
			int sharkD = fish[idx][1];
			solve(nx, ny, sharkD, sum + idx);

			//복구
			board[x][y] = 0;
			board[nx][ny] = idx;
			fish[idx][0] = 4 * nx + ny;
		}
		else break;
	}
	answer = max(answer, sum);
	//복구
	memcpy(board, dup, sizeof(dup));
	for (int i = 1; i <= 16; i++) {
		fish[i][0] = fdup[i][0];
		fish[i][1] = fdup[i][1];
	}
	return;
}
int main() {
	int x, y;
	for (int i = 0; i < 4; i++) {
		for (int j = 0; j < 4; j++) {
			cin >> x >> y;
			board[i][j] = x;
			fish[x][0] = 4 * i + j;
			fish[x][1] = y;
		}
	}

	int initN = board[0][0];
	int initD = fish[initN][1];
	fish[initN][0] = -1;
	board[0][0] = 0;
	solve(0,0,initD,initN);
	cout << answer << '\n';
}