백준 - 청소년 상어 (19236)

1. 문제

문제 링크

2. 풀이

전형적인 삼성 기출 문제 스타일입니다.
늘 하던대로 해보겠습니다.

1. 필요한 자료구조 선언

int my[9] = { -1, -1, 0, 1, 1, 1, 0, -1 };
int mx[9] = { 0, -1, -1, -1, 0, 1, 1, 1 };
int sea[MAX][MAX]; // 바다
int fishs[MAX * MAX + 1][3]; // 물고기 정보
int eaten[MAX * MAX + 1]; // 물고기 먹혔는지 여부

• my, mx: 차례대로 물고기가 회전하는 방향
• fishs: 물고기의 정보를 담는 2차원 배열
  • fishs[0][0]: 0번째 물고기의 y좌표
  • fishs[0][1]: 0번째 물고기의 x좌표
  • fishs[0][2]: 0번째 물고기의 현재 방향

가장 중요한 부분이죠.
이 부분을 어떻게 설계하느냐에 따라서 같은 문제라도 난이도가 천차만별입니다.

2. 물고기 이동 구현

// 물고기 이동
for (int i = 1; i <= MAX * MAX; i++) {
	if (eaten[i]) continue;

	int y = fishs[i][0];
	int x = fishs[i][1];
	int dir = fishs[i][2];

	for (int j = 0; j < 8; j++) {
		int ny = y + my[dir];
		int nx = x + mx[dir];

		// 범위 초과했거나 상어 있는 칸일 때 방향을 바꾸고 넘어감
		if (isOut(ny, nx) || (ny == sy && nx == sx)) {
			dir = (dir + 1) % 8;
			continue;
		}

		// 자리 교환
		fishs[i][0] = ny;
		fishs[i][1] = nx;
		fishs[i][2] = dir;
		fishs[sea[ny][nx]][0] = y;
		fishs[sea[ny][nx]][1] = x;
		swap(sea[y][x], sea[ny][nx]);

		break;
	}
}

모든 물고기를 1번부터 차례대로 움직여줍니다.
코드를 보면 쉽게 이해할 수 있을 거라 생각합니다.

3. 모든 경우의 수 다 해보기

이 부분은 전체 코드로 보겠습니다.

3. 전체 코드

#define MAX 4
#include <bits/stdc++.h>

int a, b;
int my[9] = { -1, -1, 0, 1, 1, 1, 0, -1 };
int mx[9] = { 0, -1, -1, -1, 0, 1, 1, 1 };
int sea[MAX][MAX];
int fishs[MAX * MAX + 1][3];
int eaten[MAX * MAX + 1];

using namespace std;

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

void copyA(int from[MAX][MAX], int to[MAX][MAX]) {
	for (int i = 0; i < MAX; i++)
		for (int j = 0; j < MAX; j++)
			to[i][j] = from[i][j];
}

void copyB(int from[MAX * MAX + 1][3], int to[MAX * MAX + 1][3]) {
	for (int i = 1; i <= MAX * MAX; i++) {
		to[i][0] = from[i][0];
		to[i][1] = from[i][1];
		to[i][2] = from[i][2];
	}
}

int slove(int sy, int sx, int sdir, int sum) {
	// 물고기 이동
	for (int i = 1; i <= MAX * MAX; i++) {
		if (eaten[i]) continue;

		int y = fishs[i][0];
		int x = fishs[i][1];
		int dir = fishs[i][2];

		for (int j = 0; j < 8; j++) {
			int ny = y + my[dir];
			int nx = x + mx[dir];

			// 범위 초과했거나 상어 있는 칸일 때 방향을 바꾸고 넘어감
			if (isOut(ny, nx) || (ny == sy && nx == sx)) {
				dir = (dir + 1) % 8;
				continue;
			}

			// 자리 교환
			fishs[i][0] = ny;
			fishs[i][1] = nx;
			fishs[i][2] = dir;
			fishs[sea[ny][nx]][0] = y;
			fishs[sea[ny][nx]][1] = x;
			swap(sea[y][x], sea[ny][nx]);

			break;
		}
	}

	int ret = sum;
	int tmpSea[MAX][MAX];
	int tmpFishs[MAX * MAX + 1][3];

	copyA(sea, tmpSea);
	copyB(fishs, tmpFishs);

	for (int i = 0; i < 3; i++) {
		sy += my[sdir];
		sx += mx[sdir];

		// 범위 초과면 break
		if (isOut(sy, sx)) break;

		// 이미 먹은 물고기는 넘어가기
		if (eaten[sea[sy][sx]]) continue;

		int fish = sea[sy][sx];

		eaten[fish] = 1;
		ret = max(ret, slove(sy, sx, fishs[fish][2], sum + fish));
		eaten[fish] = 0;
		copyA(tmpSea, sea);
		copyB(tmpFishs, fishs);
	}

	return ret;
}


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

	for (int i = 0; i < 4; i++) {
		for (int j = 0; j < 4; j++) {
			cin >> a >> b;

			fishs[a][0] = i;
			fishs[a][1] = j;
			fishs[a][2] = b - 1;
			sea[i][j] = a;
		}
	}

	int fish = sea[0][0];

	eaten[fish] = 1;
	cout << slove(0, 0, fishs[fish][2], fish);

	return 0;
}

단순히 상어가 다음 물고기를 먹을 수 있으면, 다시 재귀 호출로 넘기고
먹지 못하면 재귀가 종료되는 원리입니다.
주의할 점은 재귀를 빠져나오고서 이전 상태로 돌려줘야하니까
각 상태 공간마다 현재 바다의 상태, 물고기의 상태를 저장해놓고
재귀를 빠져나올 때 복구시켜줘야 합니다.